成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

LeetCode.3 無重復字符的最長子串(JS)

wthee / 2316人閱讀

摘要：先跳到第三題是因為第二題第一眼沒讀懂一題目無重復字符的最長子串給定一個字符串，請你找出其中不含有重復字符的最長子串的長度。示例輸入輸出解釋因為無重復字符的最長子串是，所以其長度為。以此來實現判斷是否包含重復字符。

先跳到第三題是因為第二題第一眼沒讀懂
一、題目

無重復字符的最長子串：

給定一個字符串，請你找出其中不含有重復字符的 最長子串 的長度。


示例1


輸入: "abcabcbb"
輸出: 3 
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。


示例2


輸入: "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。


示例3


輸入: "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3。


請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。
二、我的答案

因為這道題之前在學校刷題的時候見過類似的，大概記得解法，就先放自己的思路

v1.0 
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
  let resultLength = 0
  function hasEchoChar(str){
    return new Set(str).size !== str.length ? true : false
  }
  let begin = 0, end = 1;
  while(end <= s.length) {
    if (!hasEchoChar(s.slice(begin, end))) {
      end - begin > resultLength ? resultLength = end - begin : null;
      end++
    } else {
      begin++ 
    }
  }
  return resultLength
};

講解

兩個指針用來遍歷字符串，begin指向當前字符串的頭，end指向當前字符串的下一位

let begin = 0, end = 1

如果當前字符串不包含重復字符串，則判斷是否更新結果(resultLength)且end++，如果包含，begin++

if (!hasEchoChar(s.slice(begin, end ))) {
  end - begin > resultLength ? resultLength = end - begin : null;
  end++
} else {
  begin++ 
}

???????上文也說了之前碰到過類似的題，當時理解這部分用了好久，因為常寫的循環(huán)都是只有一個指針變量的，像for(let i = 0; i < num; i++)，如果按照慣用思路肯定是循環(huán)套循環(huán)遍歷所有子串，麻煩的丫批，上面這種寫法妙就妙在一次循環(huán)中要么更新begin要么更新end，縮小了子串的篩選范圍。

???????以示例3中的pwwkew為例，遍歷的過程如下圖

v2.0

寫完v1.0代碼，開心提交，通過是通過了，但是

???????我：？？？怎么肥四，一頓亂吹然后戰(zhàn)勝8%，神仙打架？仔細分析了一下，發(fā)現是判斷是否包含重復字符的函數hasEchoChar的問題，在v1.0代碼中我把子串轉化成set結構然后對比前后length是否相等，因為set自動去重的特性，如果相等則沒有重復字符。以此來實現判斷是否包含重復字符。(這么寫的原因是上一題做完后去看了es6中Set和Map一章，上一題分析連接:我是鏈接)

function hasEchoChar(str){
    return new Set(str).size !== str.length ? true : false
}

???????估計耗時就是耗在了轉化成set結構了，這樣寫本身并沒錯，但是他的作用是判斷一個任意字符串是否含有重復字符，我們每次判斷的是任意字符串嗎？并不是，那就不應該繼續(xù)采用這種方法。
???????聚光燈打到上文中展示遍歷過程那張圖，有重復字符的是pw->pww和wke->wkew，也就是說，只有每次end++時才有可能產生重復字符，也即是說我們只需要判斷上次遍歷的字符串是否包含這次新添加的字符即可，思路理清，代碼如下

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let resultLength = 0
  let begin = 0, end = 1
  while (end <= s.length) {
    let index = s.slice(begin, end - 1).indexOf(s[end - 1])
    if (index !== -1) {
      begin += (index + 1)
      end++
    } else {
      end - begin > resultLength ? resultLength = end - begin : null;
      end++
    }
  }
  return resultLength
};

???????同時做出優(yōu)化的部分還有找到相同字串的情況

if (index !== -1) {
  begin += (index + 1)
  end++
}

???????在v1.0的代碼中，每次找到相同字符就將begin指到下一個位置，如果還有呢，就再指向下一個位置，很明顯begin可以一次指到位，即指到與當前子串末位相同字符位置的下一位，同時end++，開始下一輪的嶄新循環(huán)。

???????至此這道題我已經竭盡所能，執(zhí)行用時從v1.0的956ms降低到v2.0的132ms，擊敗提交也從8.77%漲到71.88%。但是貪婪的我并不能滿足于71.88%，于是去復制了一份耗時最低的答案自己提交，發(fā)現耗時140ms甚至比我的耗時還要多？去查了一下(查詢結果)，可能原因為：1、服務器負載；2、測試用例增加。
???????奧~~這樣啊
???????那對不起，我的就是最佳答案

三、優(yōu)秀答案 
/**
 *. @param {string} s
 *. @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let substr = "", maxLength = 0;
    for (var i = 0; i < s.length; i++) {
        let findIndex = substr.indexOf(s[i]);
        if (~findIndex) {
            substr = substr.substring(findIndex + 1);
        }
        substr += s[i];
        if (substr.length > maxLength) {
            maxLength = substr.length;
        }
    }
    return maxLength;
};

按位取反~
之前從沒見過~符號，搜了一下，是什么補碼之類的，應該是大學計算機原理講的東西(流下了悔恨的淚水)，感興趣的小伙伴可以看一下這個js中怎么理解按位取反？

substring
功能和slice相同類似，同樣，感興趣的小伙伴可以看一下MDN中substring的定義

四、路漫漫其修遠兮

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://systransis.cn/yun/102881.html

相關文章

  • 【leetcode】3. 無重復字符的最長子串

    摘要：示例輸入輸出解釋因為無重復字符的最長子串是，所以其長度為。請注意，你的答案必須是子串的長度，是一個子序列，不是子串。完成循環(huán)后取隊列中出現的最大長度即可。 給定一個字符串，請你找出其中不含有重復字符的?最長子串?的長度。 示例?1： 輸入: abcabcbb 輸出: 3 解釋: 因為無重復字符的最長子串是 abc，所以其長度為 3。 示例 2： 輸入: bbbbb 輸出: 1 解釋:...

    qc1iu 評論0 收藏0

  • LeetCode 3——無重復字符的最長子串

    摘要：題目解答方法一我們從前往后遍歷字符串，代表最長子串的起始位置，一開始設置為零。如果沒有遇到重復字符，則更新子串的長度，向后遍歷。最長子串的起始位置重復的字符在子串中的位置初始化映射自動初始化為零獲取更多精彩，請關注 1. 題目 showImg(https://segmentfault.com/img/remote/1460000016867082); 2. 解答 2.1. 方法一 我們...

    Rocture 評論0 收藏0

  • 力扣(LeetCode)3

    摘要：示例輸入輸出解釋因為無重復字符的最長子串是，所以其長度為。請注意，你的答案必須是子串的長度，是一個子序列，不是子串。若沒有重復元素，則區(qū)間右邊擴大，否則區(qū)間左邊縮小。 題目地址：https://leetcode-cn.com/probl...題目描述：給定一個字符串，請你找出其中不含有重復字符的 最長子串 的長度。 示例 1: 輸入: abcabcbb輸出: 3 解釋: 因為無重復字符...

    _DangJin 評論0 收藏0

  • Leetcode 3 Longest Substring Without Repeat... 最長無

    摘要：難度題意是求最長無重復子串給出一個字符串從所有子串中找出最長且沒有重復字母的子串的長度我的解法是以為例使用一個記錄當前子串遇到的所有字符用一個游標從頭開始讀取字符加入到中如果碰到了重復字符遇到了重復則從當前子串的頭部的字符開始將該字符從中移 Longest Substring Without Repeating CharactersGiven a string, find the le...

    RyanHoo 評論0 收藏0

  • 前端中等算法-無重復字符的最長子串

    摘要：無重復字符的最長子串難度中等描述給定一個字符串，請你找出其中不含有重復字符的最長子串的長度。輸入輸出解釋因為無重復字符的最長子串是，所以其長度為。 無重復字符的最長子串 難度：中等 描述： 給定一個字符串，請你找出其中不含有重復字符的 最長子串 的長度。 樣例： 輸入: abcabcbb 輸出: 3 解釋: 因為無重復字符的最長子串是 abc，所以其長度為 3。 輸入: bbbbb ...

    hyuan 評論0 收藏0

發(fā)表評論

0條評論

wthee

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<