3-8 滑动窗口 Longest Substring Without Repeating Characters代码中的疑问
来源:3-8 在滑动窗口中做记录 Longest Substring Without Repeating Characters
stcheng1982
2017-09-18
老师的示例代码中 r 下标会先判断是否超出数组长度,但是一旦超出会转而去增加l下标。我的理解是一旦r到达边界(r+1超出)是循环已经可以退出,因为不会再有更长的substring了。而且r+1超出时,如果转而去增加l ,后面还会去做一次 res=max(res, r-l+1), 这个似乎是多余的,而且逻辑上也不对(虽然不会影响最终结果)
我是这样实现的:
class Solution(object):
def lengthOfLongestSubstring(self, s):
if not s or len(s) ==0:
return 0
l=0
r=-1
ssize = len(s)
charmap = [0 for i in range(128)]
maxlen = 0
while l<ssize:
if r+1 >= ssize:
break
if charmap[ord(s[r+1])]==0:
charmap[ord(s[r+1])]+=1
r+=1
maxlen = max(maxlen, r-l+1)
else:
while l<ssize and charmap[ord(s[r+1])]>0:
charmap[ord(s[l])]-=1
l+=1
return maxlen
顺便问一下对于滑动窗口的迭代,老师似乎都喜欢用左下标l 来作为循环判断条件,这个是有什么好处么(比如边界处理), 我一般习惯于用r 下标是否到边来控制循环结束。
谢谢
1回答
-
我没有仔细看你的代码,但看了你的叙述,你的思路是没有问题的。因为这个问题是求解窗口长度最长的解,所以确实在r到达边界以后就不会有新的更优解了。但是我没有理解为什么做res=max(res, r-l+1)“逻辑上也不对”?
使用左下标来判断,是因为这样其实才真正将所有的窗口都遍历了一遍。我们从初始的一个空窗口出发,经过循环迭代以后,到最终回归到了一个空窗口。在有些问题中,如果我们最优化的内容不是窗口的长度,而是窗口中的元素的某些性质的话,我们需要保证能够遍历到所有可能的窗口:)
122017-09-18
相似问题