iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 9
0
Software Development

天天 LeetCode,立地成佛:三十天從頭開始學演算法系列 第 9

[Day 9] Longest Substring Without Repeating Characters:簡單講點 two pointer

瀕臨死亡的一天,只好翻開覆蓋過的題目結束這一回合。每天都在踩線的邊緣反覆橫跳並且懷疑人生,距離脫離苦海還有三個星期(崩潰)。

還是簡單講一下,主要用到的東西是第二天講到的 dictionary,另外加上一點雙指針的概念。這題求最長的不重複子字串,可以想像成拿 A、B 兩根指針,一開始都指在最前方,然後慢慢把 B 指針往後移,指到有文字和前面的東西重複時,就停下來紀錄長度,然後反過來把 A 指針往後移,移到沒有重複的字串時(重複的字可能在字串中間,不一定在最前面),B 指針再繼續往後走,這樣持續移動。比較類似的方法還有 sliding window,但那個下次再見。


https://ithelp.ithome.com.tw/upload/images/20200916/20129662rtVnMF8Pgi.png

// javascript

var lengthOfLongestSubstring = function(s) {
    if (s.length == 1) return 1
    const dict = {}
    let num = 0
    let big = 0
    
    let start = 0
    let end = 0

    while(start < s.length && end < s.length) {
        if (dict[s[end]]) {
            big = Math.max(num,big)
            num -= 1
            delete dict[s[start]]
            start += 1
        } else {
            dict[s[end]] = true
            num += 1
            end += 1
        }

    }

    return Math.max(big,num)
};

上一篇
[Day 8] Construct Binary Tree:樹的遍歷
下一篇
[Day 10] Number of Islands:DFS 初探
系列文
天天 LeetCode,立地成佛:三十天從頭開始學演算法12
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言