我一直在最長的子字符串上花費數小時而不重復字符 - 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 算法的思想。我假設作為初學者花費數小時調試后,最終有可能解決它。
添加回答
舉報
0/150
提交
取消