LeetCode.3 無重復(fù)字符的最長(zhǎng)子串(JS)

wthee 發(fā)布于2019-08-23 16:18 / 2281人閱讀

摘要：先跳到第三題是因?yàn)榈诙}第一眼沒讀懂一題目無重復(fù)字符的最長(zhǎng)子串給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。示例輸入輸出解釋因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是，所以其長(zhǎng)度為。以此來實(shí)現(xiàn)判斷是否包含重復(fù)字符。

先跳到第三題是因?yàn)榈诙}第一眼沒讀懂

一、題目

無重復(fù)字符的最長(zhǎng)子串：

給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。
示例1
輸入: "abcabcbb"
輸出: 3 
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。
示例2
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1。
示例3
輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "wke"，所以其長(zhǎng)度為 3。
請(qǐng)注意，你的答案必須是 子串 的長(zhǎng)度，"pwke" 是一個(gè)子序列，不是子串。

二、我的答案

因?yàn)檫@道題之前在學(xué)校刷題的時(shí)候見過類似的，大概記得解法，就先放自己的思路

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
};

講解

兩個(gè)指針用來遍歷字符串，begin指向當(dāng)前字符串的頭，end指向當(dāng)前字符串的下一位

let begin = 0, end = 1

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

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

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

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

v2.0

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

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

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

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

/**
 * @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
};

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

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

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

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

三、優(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;
};

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

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

四、路漫漫其修遠(yuǎn)兮

云服務(wù)器 GPU云服務(wù)器最長(zhǎng)公共子串 java最長(zhǎng)相同子串字符串找子串算法字符串最大子串c語(yǔ)言

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/102881.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

wthee

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

C語(yǔ)言define和初級(jí)指針

閱讀 2403·2021-10-14 09:43
????新生代農(nóng)民工爆肝8萬字，整理Python編程從入門到實(shí)踐(建議收藏)已碼：6萬字????

閱讀 2434·2021-09-09 09:34
CSS 加載新方式

閱讀 1601·2019-08-30 12:57
【CSS】nth-child 與 nth-of-type辨析

閱讀 1198·2019-08-29 14:16
注冊(cè)和登錄（關(guān)于Cookie）

閱讀 716·2019-08-26 12:13
PHP與AJAX的相愛相殺

閱讀 3200·2019-08-26 11:45
LeetCode.3 無重復(fù)字符的最長(zhǎng)子串(JS)

閱讀 2282·2019-08-23 16:18
為什么編程語(yǔ)言的都要定義數(shù)據(jù)類型

閱讀 2652·2019-08-23 15:27

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

LeetCode.3 無重復(fù)字符的最長(zhǎng)子串(JS)

示例1

示例2

示例3

相關(guān)文章