@liweiwei1419
2019-05-24T08:37:28.000000Z
字数 2988
阅读 1955
动态规划
滑动窗口
散列表
传送门:3. 无重复字符的最长子串。这道题也是《剑指Offer》上第 48 题。
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
判断一个元素有没有出现过,使用哈希表是最自然的想法。
以下面的例子进行说明:
判断连续区间内是否出现重复元素,可以使用 set
,又要存储位置,所以使用 dict
。
Python 代码1:(推荐写法)
等价的写法:(我的练习)
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
map = dict()
max_len = 0
# 可以认为是标定的起始
pointer = 0
for index, c in enumerate(s):
if c in map:
pointer = max(pointer, map[c] + 1)
max_len = max(max_len, index - pointer + 1)
# 每次遍历都更新当前遍历到的字母的位置
map[c] = index
return max_len
if __name__ == '__main__':
s = 'pwwkew'
solution = Solution()
result = solution.lengthOfLongestSubstring(s)
print(result)
需要注意的一点是:只有重复出现的位置大于标定点的时候,才要更新,更新的位置是当前位置 + 1。即只要出现重复,隔板就向后移动一位,然后每一轮都计算当前与隔板的距离。
Python 代码2:(不如上面的代码语义清晰)
class Solution:
def lengthOfLongestSubstring(self, s):
# 特判
l = len(s)
if l < 2:
return l
# 隔板法
# key:字符,val 出现的索引
map = dict()
point = 0
res = 1
for i in range(l):
# 关键1:map[s[i]] >= point,等于是可以的
if s[i] in map and map[s[i]] >= point:
# 先把隔板向后移动一位
point = map[s[i]] + 1
# 然后记录最长不重复子串的长度
res = max(res, i - point + 1)
# 关键2:无论如何都更新位置
map[s[i]] = i
return res
等价的写法:(我的练习)
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
l = len(s)
if l <= 1:
return l
point = 0
map = dict()
result = 0
for index, alpha in enumerate(s):
if alpha in map and map[alpha] >= point:
point = map[alpha] + 1
# 每次要做两件事:1、计算无重复子串长度
result = max(result, index - point + 1)
# 2、更新索引
map[alpha] = index
return result
dp[i]:以 s[i] 结尾的最长不重复子串,这个状态的设置与最长上升子序列、最大连续子数组是一样的。
下面考虑 dp[i] 和 dp[i-1] 之间的关系。关键在于 dp [i-1] 与距离出现相同字符的时候,两个相同字符的距离的比较。
Python 代码:
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 特判
l = len(s)
if l < 2:
return l
# dp[i] 表示以 s[i] 结尾的最长不重复子串的长度
# 因为自己肯定是不重复子串,所以初始值设置为 1
dp = [1 for _ in range(l)]
map = dict()
map[s[0]] = 0
for i in range(1, l):
if s[i] in map:
if i - map[s[i]] > dp[i - 1]:
dp[i] = dp[i - 1] + 1
else:
dp[i] = i - map[s[i]]
else:
dp[i] = dp[i - 1] + 1
# 设置字符与索引键值对
map[s[i]] = i
# 最后拉通看一遍最大值
return max(dp)
Python 代码:推荐写法
# 滑动窗口的做法
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 特判
size = len(s)
if size < 2:
return size
l = 0
r = -1
counter = [0 for _ in range(256)]
res = 1
while l < size:
# 尝试走一步,如果可以走,就计算
if r + 1 < size and counter[ord(s[r + 1])] == 0:
# 表示没有重复元素,r 可以加 1
counter[ord(s[r + 1])] += 1
r += 1
else:
# 有重复元素,左边就要减 1
counter[ord(s[l])] -= 1
l += 1
res = max(res, r - l + 1)
return res
Python 代码:滑动窗口写法2
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 特判
size = len(s)
if size < 2:
return size
l = 0
r = -1
counter = [0 for _ in range(256)]
res = 1
while l < size:
# 首先"右指针"不断向右边尝试,走到出现重复的最右边
while r + 1 < size and counter[ord(s[r + 1])] == 0:
# 表示没有重复元素,r 可以加 1
counter[ord(s[r + 1])] += 1
r += 1
# 此时,记录不重复子串是"左指针"固定时候最长
res = max(res, r - l + 1)
# 考虑移动"左指针"
# 此时 s[r+1] 就是已经扫过的区间里重复的元素,要把它剔除出去
while r + 1 < size and s[l] != s[r + 1]:
# 有重复元素,左边就要减 1
counter[ord(s[l])] -= 1
l += 1
# 出了上一个循环以后,还要再把左指针向右移动一格,否则右指针不能向右移动
counter[ord(s[l])] -= 1
l += 1
return res
(本节完)