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

zgbgx 發布于2019-08-23 13:42 / 2091人閱讀

摘要：當循環到的時候，記錄一下這個最后一次出現的位置在哪里。最后，這道算法題的出處來自里面有各種各樣的實現方法，可以作為參考。覺得本文對你有幫助請分享給更多人關注妙味前端加星標，關注更多內容

尋找最長的不含有重復字符的子串

可能看標題不會明白這個題到底什么意思，來看看下面的例子：

abcabcbb ? abc ? 3

bbbb ? b ? 1

pwwkew ? wke ? 3

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

其實需求很簡單，實現的方法也很多，不過在這里我要來寫一種效率最高的算法，只需要一次循環就可解決：

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

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

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

此時咱們開始使用 for 循環掃描整個字符串，當掃描到 x（x 代表任意位置的任意的字符串）的時候，那么咱們應該怎么做呢？

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

那么怎么做到檢查這個動作呢?

這個時候 lastPositions 就派上用場了。當循環到 x 的時候，記錄一下這個 x 最后一次出現的位置在哪里。

那么記錄完畢之后，當進行檢查 start 到 x 之間是否有重復的 x 的時候，咱們就去問 lastPositions[x]，此時會有2種情況：

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

第二種情況是 x 出現在 start 到 x 中間。

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

總結下來就是：

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

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

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

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

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

里面有各種各樣的實現方法，可以作為參考。

覺得本文對你有幫助？請分享給更多人

關注【妙味前端】加星標，關注更多內容

云服務器 GPU云服務器可能不知道地方最難的算法題最小二乘擬合的算法效率最高頻率單詞算法

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/99409.html

一道有意思的面試算法題

摘要：解決方案異或操作異或運算是對于二進制數字而言的，比如說一個有兩個二進制，如果兩個值不相同，則異或結果為。比如說，本質上其實是和的每一對比特位執行異或操作，等價于下面數字對應的二進制數字對應的二進制數字對應的二進制因此的結果就為啦。新年第一篇文章，先祝大家新年快樂！！那么接下來進入正文。前言前陣子突發奇想，突然開始刷leetcode。其中刷到了一道有意思的題目，發現這道題是當時秋招...

maxmin 2019-08-23 14:28 評論0 收藏0
一道看似簡單的面試題

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

kid143 2019-07-01 10:21 評論0 收藏0
從一道前端面試題談起

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

darkbaby123 2019-08-23 17:53 評論0 收藏0
前端--通用知識 - 收藏集 - 掘金

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

王笑朝 2019-08-20 16:57 評論0 收藏0