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

資訊專欄INFORMATION COLUMN

前端算法題 | 這道題效率最高的算法，你可能不知道？

zgbgx / 2099人閱讀

摘要：當(dāng)循環(huán)到的時(shí)候，記錄一下這個(gè)最后一次出現(xiàn)的位置在哪里。最后，這道算法題的出處來自里面有各種各樣的實(shí)現(xiàn)方法，可以作為參考。覺得本文對(duì)你有幫助請(qǐng)分享給更多人關(guān)注妙味前端加星標(biāo)，關(guān)注更多內(nèi)容

尋找最長(zhǎng)的不含有重復(fù)字符的子串

可能看標(biāo)題不會(huì)明白這個(gè)題到底什么意思，來看看下面的例子：

abcabcbb ? abc ? 3

bbbb ? b ? 1

pwwkew ? wke ? 3

看了栗子是不是明白了呢？

其實(shí)需求很簡(jiǎn)單，實(shí)現(xiàn)的方法也很多，不過在這里我要來寫一種效率最高的算法，只需要一次循環(huán)就可解決：

function findNoRepeatMaxLenStr (str) {
  let lastPositions = {}
  let start = 0
  let maxLen = 0

  for (let i=0; i= start) {
              start = lastPositions[s] + 1
        }
        if (i - start + 1 > maxLen) {
              maxLen = i - start + 1
        }
    lastPositions[s] = i
  }
  return maxLen
}

// test
console.log(findNoRepeatMaxLenStr("abcabcbb"))  // 3

那么看完代碼，請(qǐng)自己先胡思亂想一下，能看得懂不？
…

行了，看到這我就知道你沒看懂，那么來解釋一下吧。
思路是這樣的，假如下面的圖形是一個(gè)字符串，每個(gè)格子代表一個(gè)字符：

此時(shí)咱們開始使用 for 循環(huán)掃描整個(gè)字符串，當(dāng)掃描到 x（x 代表任意位置的任意的字符串）的時(shí)候，那么咱們應(yīng)該怎么做呢？

首先要記錄一個(gè) start 起始位置，當(dāng)然一開始就是 0 了，那么 start 在循環(huán)中不僅僅只是表示字符串從 0 開始，還表示當(dāng)前不含有最長(zhǎng)重復(fù)子串的開始，那么咱們要做的事情就一件：保證從 start 到 x 之間沒有重復(fù)的字符串，再說的通俗點(diǎn)就是看檢查 start 到 x 之間有沒有重復(fù)的 x 。

那么怎么做到檢查這個(gè)動(dòng)作呢?

這個(gè)時(shí)候 lastPositions 就派上用場(chǎng)了。當(dāng)循環(huán)到 x 的時(shí)候，記錄一下這個(gè) x 最后一次出現(xiàn)的位置在哪里。

那么記錄完畢之后，當(dāng)進(jìn)行檢查 start 到 x 之間 是否有重復(fù)的 x 的時(shí)候，咱們就去問 lastPositions[x]，此時(shí)會(huì)有2種情況：

第一種情況是 x 從來沒有出現(xiàn)過或者出現(xiàn)在了 start 之前；

第二種情況是 x 出現(xiàn)在 start 到 x 中間。

那么對(duì)于第一種情況，咱們不用去管。而第二種情況自然是不滿足條件的情況了，此時(shí)，咱們就要更新 lastPositions[x]，將這個(gè) x 的位置更新為 lastPositions[x] + 1。

總結(jié)下來就是：

lastPositions[x] 不存在或 < start 滿足條件，無需操作

lastPositions[x] 存在并且 >= start 不滿足條件，更新 lastPositions[x]++

那么在結(jié)合上面的代碼，邏輯就清晰了，唯一有些繞圈圈的地方就是第二個(gè) if 中的 +1 操作，原因就是字符串的索引是從 0 開始的，那么假如第一個(gè)為 x 滿足條件，實(shí)際索引是0，那么長(zhǎng)度應(yīng)該是 0 + 1 = 1。

最后，這道算法題的出處來自：

https://leetcode.com/problems...

里面有各種各樣的實(shí)現(xiàn)方法，可以作為參考。

覺得本文對(duì)你有幫助？請(qǐng)分享給更多人

關(guān)注【妙味前端】加星標(biāo)，關(guān)注更多內(nèi)容

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

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

相關(guān)文章

  • 一道有意思的面試算法題

    摘要：解決方案異或操作異或運(yùn)算是對(duì)于二進(jìn)制數(shù)字而言的，比如說一個(gè)有兩個(gè)二進(jìn)制，如果兩個(gè)值不相同，則異或結(jié)果為。比如說，本質(zhì)上其實(shí)是和的每一對(duì)比特位執(zhí)行異或操作，等價(jià)于下面數(shù)字對(duì)應(yīng)的二進(jìn)制數(shù)字對(duì)應(yīng)的二進(jìn)制數(shù)字對(duì)應(yīng)的二進(jìn)制因此的結(jié)果就為啦。 新年第一篇文章，先祝大家新年快樂?。∧敲唇酉聛磉M(jìn)入正文。 前言 前陣子突發(fā)奇想，突然開始刷leetcode。其中刷到了一道有意思的題目，發(fā)現(xiàn)這道題是當(dāng)時(shí)秋招...

    maxmin 評(píng)論0 收藏0

  • 一道看似簡(jiǎn)單的面試題

    摘要：二進(jìn)制本身就是為這個(gè)數(shù)字而使用的，所以說這道面試題直指二進(jìn)制的使用是沒錯(cuò)的。正負(fù)在二進(jìn)制中，第一位為的是負(fù)數(shù)，是正數(shù)。 showImg(https://segmentfault.com/img/bVbd7d0?w=1580&h=732); 前言 使用PHP,給定一個(gè)數(shù),判斷這個(gè)數(shù)是否是二的N次方 這樣看似簡(jiǎn)單的一個(gè)面試題, 實(shí)際牽出了很多基礎(chǔ)知識(shí),本章在為大家補(bǔ)習(xí)基礎(chǔ)知識(shí)的情況下來解答...

    kid143 評(píng)論0 收藏0

  • 從一道前端面試題談起

    摘要：但是題目非要弄成鏈表的形式，說實(shí)在的，我真沒有見過前端什么地方還需要用鏈表這種結(jié)構(gòu)的除了面試的時(shí)候，所以說這種題目對(duì)于實(shí)際工作是沒什么用處的，但是腦筋急轉(zhuǎn)彎的智商題既然這樣出了，我們就來看看怎么解決它吧。 今天在知乎上看到一個(gè)回答《為什么前端工程師那么難招？》，作者提到說有很多前端工程師甚至連單鏈表翻轉(zhuǎn)都寫不出來。說實(shí)話，來面試的孩子們本來就緊張，你要冷不丁問一句單鏈表翻轉(zhuǎn)怎么寫，估計(jì)...

    darkbaby123 評(píng)論0 收藏0

  • 前端--通用知識(shí) - 收藏集 - 掘金

    摘要：閉包有多重前端知識(shí)點(diǎn)大百科全書前端掘金，，技巧使你的更加專業(yè)前端掘金一個(gè)幫你提升技巧的收藏集。 Vue全家桶實(shí)現(xiàn)還原豆瓣電影wap版 - 掘金用vue全家桶仿寫豆瓣電影wap版。 最近在公司項(xiàng)目中嘗試使用vue，但奈何自己初學(xué)水平有限，上了vue沒有上vuex，開發(fā)過程特別難受。 于是玩一玩本項(xiàng)目，算是對(duì)相關(guān)技術(shù)更加熟悉了。 原計(jì)劃仿寫完所有頁(yè)面，礙于豆瓣的接口API有限，實(shí)現(xiàn)頁(yè)面也有...

    王笑朝 評(píng)論0 收藏0

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

0條評(píng)論

zgbgx

男|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<