每日一题【20220402】

昨天学长抛一个题目，自己想了想，刚开始以为只是看不重复的字符，依稀记得当时学过一个保存不重复的数组的，以为就是要实现一下去重计数，没看懂还要求连续，查了查，发现是LeetCode题库第三题，是求无重复最大字串长度。想起来当时准备建模自己博客还写过每日一题栏目，现在又想再继续写下去了，记录一下自己的刷题记录，也希望自己能够坚持下去……..

题目描述

给定一个字符串，找出不含有重复字符的最长子串的长度。

示例：
给定 “abcabcbb” ，没有重复字符的最长子串是 “abc” ，那么长度就是 3。
给定 “bbbbb” ，最长的子串就是 “b” ，长度是 1。
给定 “pwwkew” ，最长子串是 “wke” ，长度是 3。请注意答案必须是一个子串，”pwke” 是 子序列 而不是子串。

1.暴力求解

先两层遍历把所有的连续的子串保存出来，然后设计一个判断函数，判断每个字符串中是否有重复，若有重复直接跳过，若没重复，用一个当前长度保存其长度，再与最大长度作比较，保留较大的值。

1
2
3
4
5
6
7
8
a=[]
res_s=''
str="2pw ak85ew"
for i in range(len(str)):
    for j in range(len(str)):
        if j>i:
            a.append(str[i:j])
print(a)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
cur_len=0;
max_len=0;
for i in range(len(a)):
    list(a[i])
    flag=0;
    for j in range(len(a[i])):
        for k in range(len(a[i])):
            if k>j:
                if a[i][k]==a[i][j]:
                    flag=0;
                else:
                    flag=1;
    if flag==1:
        cur_len=len(a[i])
        if max_len<cur_len:
            max_len=cur_len
            res_s=a[i]
print(max_len)
print(res_s)

flag那个地方想了一会，因为是两层for循环，用break感觉还是会继续比较，最后还是要添加flag，所以没有任何意义，就索性直接让他挨个遍历跑了一遍，最后看flag的情况。不得不说，flag确实yyds。但是实现的时候，可能是自己逻辑能力还不太行，对封装函数有点欠缺，全写在一个函数里有点绕，趁一大早脑回路清晰，才得以实现了他……

记坑

后来换了个参数，发现自己前面这个也做错了，重新理了理思路，大概是flag那里有问题，干脆抽出了写个判断有无重复的函数，再for循环遍历无重复的元素，进行记录最长连续子串长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#前面遍历输出整个连续子串没问题
a=[]
str="abcbae"
for i in range(len(str)):
    for j in range(len(str)):
        if j>=i:
            a.append(str[i:j+1])
#print(a)
#print(len(a))
#print(a[1])

#封装判断函数
def judge(str):
    flag=1
    for j in range(len(str)):
            for k in range(len(str)):
                if k>j:
                    if str[k]==str[j]:
                        flag=0
                        break
            if flag==0:
                break
    return flag

#输出最长连续子串长度
res_s=[]
max_len=0
flag=2
for i in range(len(a)):
    #print(judge(a[i]))
    flag=judge(a[i])
    if flag==1:
        if max_len<len(a[i]):
            max_len=len(a[i])
            res_s=a[i]
print(max_len)
print(res_s)

暴力优化

感谢师哥的引导。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import math
max_len=-math.inf
a=set()
str="abcbae"
for i in range(len(str)):
    for j in range(len(str)):
        if j>=i:
            for k in range(i,j+1):
                a.add(str[k])
                if(len(a)==j+1-i):
                    if max_len<len(a):
                        max_len=len(a)
                        res_s=a
print(max_len)
print(res_s)

image-20220412182446595

不过set也有坏处，就是顺序没有了。

2.优化算法

把字符一个个放入一个数组里，如果该字符（重复字符）在数组中，删除数组索引0到该字符的索引，用一个当前长度保存其长度，再与最大长度作比较，保留较大的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
s='2pw ak85ew'
res_s=''
a=[]
max_len=0;
for i in range(len(s)):
    if s[i] in a:
        a=a[i+1:]    #此处i是原str第i个元素，而不是出现重复的字符的索引
    else:
        a.append(s[i])
    if max_len<len(a):
        max_len=len(a)
        res_s=a
print(max_len)
print(res_s)

后来换了个序列跑发现有问题，于是增加了一个index量，记录出现字符元素的索引位置，因为这次遍历也占用一次遍历，而且前面的重复元素被删了，所以这一步里也需要增加当前遍历的元素，即第i个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
s='abcbae'
res_s=''
a=[]
max_len=0;
for i in range(len(s)):
    #print(i)
    if s[i] in a:
        index=a.index(s[i])
        a=a[index+1:]
        a.append(s[i])
        #print(a)
    else:
        a.append(s[i])
    if max_len<len(a):
        max_len=len(a)
        res_s=a
        #print(res_s)
print(max_len)
print(res_s)

3.滑动窗口

滑动窗口算法（Sliding Window Algorithm）
Sliding window algorithm is used to perform required operation on specific window size of given large buffer or array.
滑动窗口算法是在给定特定窗口大小的数组或字符串上执行要求的操作。
This technique shows how a nested for loop in few problems can be converted to single for loop and hence reducing the time complexity.
该技术可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。

刚开始看到了这个概念，简单看了看，满脸问号，自己在纸上给了两个例子一步步跑了跑，发现确实很巧妙。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
s='abcbae'
l=0
r=0
cur_len=0
max_len=0
substring=[]
while l<len(s) and r<len(s):
    if s[r] in substring:
        substring.remove(s[l])
        l+=1
    else:
        substring.append(s[r])
        r+=1
        cur_len=r-l
        if cur_len>max_len:
            max_len=cur_len
            res_str=substring
print(max_len)
print(res_str)

个人理解：两个指针来界定范围，并以右指针为主指针不断增加范围，左指针用来做判断，使得界定范围内没有重复元素并且只保留连续的无重复子串。

参考资料

  1. 暴力解王|无重复字符的最长子串 ↩
  2. LeetCode题解|3.无重复字符的最长子串 ↩
学习 > python
#python #LeetCode #力扣 #刷题 #每日一题 #滑动窗口
每日一题【20220402】
https://blog.baixf.tk/2022/04/02/每日一题/每日一题【20220402】/
作者
白小飞
发布于
2022年4月2日
许可协议