亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

不重復字符的最長子串

不重復字符的最長子串

忽然笑 2022-01-18 16:37:13
我一直在最長的子字符串上花費數小時而不重復字符 - LeetCode不重復字符的最長子串中等的給定一個字符串,找出最長的不重復字符的子串的長度。示例 1:Input: "abcabcbb"Output: 3 Explanation: The answer is "abc", with the length of 3. 示例 2:Input: "bbbbb"Output: 1Explanation: The answer is "b", with the length of 1.示例 3:Input: "pwwkew"Output: 3Explanation: The answer is "wke", with the length of 3.              Note that the answer must be a substring, "pwke" is a subsequence and not a substring.可以使用兩個指針混合 kadane 的算法來操作子數組來解決該問題class Solution:    def lengthOfLongestSubstring(self, s: str) -> int:        logging.debug(f"{list(enumerate(s))}")        slo = fas = 0  #slow as the fisrt character in a subarray which not duplicate, fast as the fast.                                  #relation: length = fas - slo        current = set()        glo = loc = 0        while fas < len(s):            logging.debug(f"pre_current: {current}, slow: {slo}, fast: {fas}")            if s[fas] not in current:                 current.add(s[fas]                loc = fas - slo                glo = max(glo, loc)                 fas +=1            else:                current.remove(s[slo])                slo += 1            logging.debug(f"post_current: {current}, slow: {slo}, fast: {fas} \n")        return glo測試用例    def test_g(self):        s = "abccefg"        answer = 4        check = self.solution.lengthOfLongestSubstring(s)        self.assertEqual(answer, check)解決方案很清楚慢速和快速交替移動$ python 3.LongestSubstring.py MyCase.test_gDEBUG [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'c'), (4, 'e'), (5, 'f'), (6, 'g')]DEBUG pre_current: set(), slow: 0, fast: 0DEBUG post_current: {'a'}, slow: 0, fast: 1 DEBUG pre_current: {'a'}, slow: 0, fast: 1DEBUG post_current: {'b', 'a'}, slow: 0, fast: 2 DEBUG pre_current: {'b', 'a'}, slow: 0, fast: 2DEBUG post_current: {'b', 'c', 'a'}, slow: 0, fast: 3 ----------------------------------------------------------------------Ran 1 test in 0.001s作為結論,該解決方案采用了兩個指針技術和 Kadane 算法的思想。我假設作為初學者花費數小時調試后,最終有可能解決它。
查看完整描述

1 回答

?
largeQ

TA貢獻2039條經驗 獲得超8個贊

如第二種方法中解決方案的評論中所述:

慢是第一個在子數組中不重復的

快速是子數組中不重復的最后一個

它使用 2 個指針來跟蹤沒有重復字符的窗口大小。如果找到重復項,它會相應地更新指針。

換句話說,它維護一個窗口并進一步滑動它們以查看它可以與non-repeating characters屬性一起使用多長時間。所以,這種方法被稱為滑動窗口技術。

這對于只有 26 個字母字符的字符串可能看起來微不足道,但對于UTF-8類型的字符串非常有用。


查看完整回答
反對 回復 2022-01-18
  • 1 回答
  • 0 關注
  • 198 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號