刷题

1. 无重复字符的最长子串

  • 滑动窗口方法

    滑动窗口的思路：利用左右指针表示字符串某个子串的左右边界。窗口是指左右指针形成的闭合区间。

    题目：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

    分析：子串是连续的且要求不能出现重复的字符，考虑到使用两个指针划定区间，首先左指针确定开始位置，右指针依次移动直至出现重复字符或到达字符串尾部，每次移动一次右指针，哈希表中就要增加一个字符。然后依次移动左指针的位置直至到达字符串尾部，每次移动一次左指针，哈希表中就删除一个字符。在每次右指针移动结束后，记录以左指针开始的位置，右指针结束的位置。这就是在当前左指针开始位置的不包含重复字符的子串。

    从上述分析可知，需要两层循环，外层循环用于移动左指针，内层循环用于移动右指针。除此之外，需要一个哈希表用于存储子串（哈希表中不能有重复元素）。

    • 代码步骤

      1）定义哈希表hash，用于存储子串。定义右指针r_k和最长子串的长度ans。

      2）两层循环遍历。外层循环遍历[0:n)左指针，内层循环遍历右指针（直至移动到字符串尾部或右指针所指字符出现在哈希表中）。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            hash = set() # 哈希表，无重复字符
            n = len(s)
            r_k, ans = 0,0 # 右指针，结果
            for l_k in range(n):     
                if l_k!=0: # 左指针，除第一轮外，均需从哈希表中去除第一位（因为，下方while的停止条件是，右指针发现了相同字符或已经访问完字符串）
                    hash.remove(s[l_k-1])
                while r_k<n and s[r_k] not in hash: 
                    # 右指针持续后移，直至字符串访问完毕或指针所指字符与哈希表中的字符相同
                    hash.add(s[r_k])
                    r_k+=1
                ans = max(ans,r_k-l_k)
                
            return ans

​

2. 最长回文子串

  • 动态规划（DP）方法

    DP的思路： 利用原问题与子问题的关系，将其变成 大问题的解 = 小问题的解的函数， 从而将问题变成size的扩展即可，当size到达最大后，原问题解决了。大问题划分为小问题

    题目：给你一个字符串 s，找到 s 中最长的回文子串。

    分析：回文串去掉头尾字符后，仍然是回文串。即，若一个字符串的头尾字符不相等，那么这个字符串一定不是回文串。

    • 大问题：字符串是否为回文串

    • 小问题：字符串去掉头尾字符后，是否为回文串，且头尾字符必须相等

    • 定义状态：dp[i][j]表示子串s[i...j]是否为回文子串，s[i...j]表示区间

    • 状态转移矩阵：dp[i][j]，由于s[i...j]表示子串，因此j>=i，只需填写矩阵的上三角

    • 状态转移方程：dp[i][j]=dp[i+1,j-1] and (s[i]==s[j])

    • 考虑两种情况：

      1）当s[i+1...j-1]的长度小于2时（无法构成区间），即j-1-(i+1)+1<2，推导为j-i<3。s[i+1,j-1]是一个字符或不存在，若s[i]==s[j]，则S[i...j]一定是回文子串。

      2）当s[i+1...j-1]的长度大于2时，则需要判断dp[i+1][j-1]是否为True（s[i+1...j-1]是否为回文子串）并且还需判断s[i]==s[j]。

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
class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 1.特殊情况
        n = len(s)
        if n<2:
            return s
        # 2.定义子串开始位置和最大长度
        begin = 0
        max_len =1
        # 3.定义转移矩阵(二维)dp
        dp = [[False]*n for _ in range(n)]
        # 4.动态规划（二维矩阵更新过程）
        for j in range(1,n):
            for i in range(0,j):
                if s[i]!=s[j]:
                    dp[i][j]=False
                else:
                    if j-i<3:
                        dp[i][j]=True
                    else:
                        dp[i][j]=dp[i+1][j-1]
                # 只要dp[i][j]为True就更新子串和其最大长度
                if dp[i][j]==True and j-i+1>max_len:
                    begin = i
                    max_len = j-i+1
        return s[begin:begin+max_len]

3. 字母异位词分组

  • HashMap方法

    字母异位词：将字符串中的字符按照字母顺序排序后，得到相同的字母列表。例如’are’和’rae’，排序后都为’aer’

    题目：给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

    分析：HashMap的键存储排序后的字母组成的字符串，值存储一个列表（用于存储相同字母列表的字母异位词）

    • 遍历每一个单词，通过排序建立HashMap的键

    • 判断键是否存在于HashMap中，考虑两种情况：

      1）存在，按照键，添加到对应的值列表中

      2）不存在，键值添加到HashMap中。

    注意：键不存在时，值用List存储，因为一个键可能对应多个值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 定义一个字典，用于存储字母异位词分组结果
        anagram_dict = {}
        
        # 遍历所有单词
        for word in strs:
            # 将单词按照字母顺序排序，并作为键
            sorted_word = ''.join(sorted(word))
            
            # 如果该键已经在字典中，将当前单词加入到对应的列表中
            if sorted_word in anagram_dict:
                anagram_dict[sorted_word].append(word)
            else:
                # 如果该键不存在，则创建新的列表，并将当前单词加入其中
                anagram_dict[sorted_word] = [word]
        
        # 返回字典中所有值组成的列表，即为结果
        return list(anagram_dict.values())

4. 最长连续序列

  • HashMap方法

    题目：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。要求时间复杂度为O(n)。

    分析：HashMap的键存储数组中的数字，值存储连续区间的长度

    • 用哈希表存储每个端点值对应连续区间的长度

    • 若数已在哈希表中：跳过不做处理

    • 若是新数加入：

      • 取出其左右相邻数已有的连续区间长度 left 和 right
      • 计算当前数的区间长度为：cur_length = left + right + 1
      • 根据 cur_length 更新最大长度 max_length 的值
      • 更新区间两端点的长度值（因为连续区间内的中间数字不会再被访问）

    注意：需要判断num是否在字典中，在的话说明该num有连续区间长度，无需计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
        def longestConsecutive(self, nums: List[int]) -> int:
        #键：list中的数值
        #值：连续区间的长度
        hash_dict = dict()

        max_length = 0
        for num in nums:
            if num not in hash_dict:
                #比num小1和大1的值是否在hash字典中，在取其对应的value，不在为0
                #在hash字典中，说明这个值有连续区间，其连续区间的大小保存在value中
                left = hash_dict.get(num-1,0)
                right = hash_dict.get(num+1,0)
                #左右两个连续区间的长度+当前数字的长度(1)
                cur_length = 1+left+right
                max_length = max(max_length,cur_length)
                #更新当前数字的连续区间长度
                #更新左右端点数字的连续区间长度
                #num-left相当于连续区间左端点的数字
                hash_dict[num] = cur_length
                hash_dict[num-left] = cur_length
                hash_dict[num+right] = cur_length
                #只更新端点数字的长度是因为连续区间内的中间数字不会再被访问
        return max_length

5. 移动零

  • 双指针方法

    题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。要求时间复杂度为O(n)。

    分析：指针i遍历整个数组，指针j记录当前有多少非0元素

    • 第一次遍历，遍历整个数组。i指针遇到非0元素，就替换j指针所指元素且j指针后移。（保证j指针之前的元素都是非0元素）
    • 第二次遍历，遍历j指针之后的数组。将所有元素置为0（因为非0元素已经替换到了j指针的前面）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        #双指针，i遍历整个列表，j记录最后一个非0元素
        n = len(nums)
        j =0
        for i in range(n):
            # i指示的元素不为0，就和j指示的元素换位
            if nums[i]:
                nums[j]=nums[i]
                j+=1
            #从j指示的非0元素起，将后续的元素全置为0
            #因为上个循环j+1了，因此下面循环直接从j开始
        for i in range(j,n):
            nums[i]=0

6. 盛最多水的容器

  • 双指针方法

    题目：给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。要求时间复杂度为O(n)。

    分析：左指针left，右指针right

    • 初始化左右指针，左指针为0，右指针为len(height)-1
    • 遍历数组的条件是left<right
      • 计算面积，长为两个指针对应的线中宽度最小的（木桶原理）min(height[left],height[right])，宽为两个指针的距离right-left
      • 判断左右指针对应的线的宽度，哪个宽度小，哪个指针移动（寻找宽度大的线）

    注意：循环的条件是左指针比右指针小，不用把整个List遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxArea(self, height: List[int]) -> int:
        #双指针，头和尾
        left,right = 0,len(height)-1
        ans = 0
        while left<right:
            #两个宽中选最小的宽*长
            area = min(height[left],height[right])*(right-left)
            ans = max(ans,area)
            #哪个宽小，哪个指针就移动
            if height[left]<=height[right]:
                left+=1
            else:
                right-=1
        return ans

7. 三数之和

  • 双指针方法

    题目：给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。

    分析：一个循环用于遍历数组中的元素，固定住一个数nums[i]，找寻两个数nums[i+1]和nums[n-1]，满足两个数之和=0-nums[i]。双指针用于搜寻满足条件的两个数。构造一个列表reslut用于存储结果。

    • 特殊判定，如果数组的大小<3，则返回[]（不足三个数，不可能满足三数之和为0）
    • 对数组进行排序（升序排序）
    • 遍历排序后的数组
      • 设定左右指针，开始和结束位置为当前顺序i的后一位到数组最后一位。
      • 特殊判定：1)去除重复元素。2）当nums[i]>0时，说明数组后面的数值均>0，不可能再有满足三数之和为0的三个数。返回reslut。
      • 双指针循环，while L<R
        • 判断三数之和nums[i]+nums[L]+nums[R]
          • 三数之和=0，将三个数加入到reslut列表中。去除重复元素，设置while，条件是L<R and L和L+1的元素相等/R和R-1的元素相等。相等的就移动指针L=L+1/R=R-1。双指针移动。
          • 三数之和<=0，说明当前三数的和小，需要一个大一些的数，移动左指针。L=L+1
          • 三数之和>0，说明当前三数的和大，需要一个小一些的数，移动右指针。R=R-1
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
class Solution:
   def threeSum(self, nums: List[int]) -> List[List[int]]:
        #特殊情况
        n=len(nums)
        res=[]
        #nums为空或元素个数少于3，返回空集
        if (not nums) or n<3:
            return []
        nums.sort() #升序排序
        for i in range(n):
            #i之后的所有元素都>0，不可能再有三个数之和为0，因此直接返回结果
            if nums[i]>0:
                return res
            #重复元素跳过
            if i>0 and nums[i]==nums[i-1]:
                continue
            L=i+1
            R=n-1
            while L<R:
                #当三者之和=0时，插入元素
                if nums[i]+nums[L]+nums[R] == 0:
                    res.append([nums[i],nums[L],nums[R]])
                    #同时满足三者之和为0的重复元素需要跳过
                    while L<R and nums[L]==nums[L+1]:
                        L+=1
                    while L<R and nums[R]==nums[R-1]:
                        R-=1
                    #指针移动
                    L+=1
                    R-=1
                #当三者之后>0时，右指针左移（元素数值减小）
                elif nums[i]+nums[L]+nums[R]>0:
                    R-=1
                #反之，左指针右移（元素数值增大）
                else:
                    L+=1
        return res

8. 接雨水

  • 双指针方法

    题目：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

    分析：定义 left[i] 表示下标 i位置及其左边的最高柱子的高度，定义 right[i]表示下标 i位置及其右边的最高柱子的高度。那么下标 i位置能接的雨水量为 min(left[i],right[i])−height[i]。我们遍历数组，计算出 left[i] 和 right[i]，最后答案为 $\sum \limits_{i=0}^{n-1}=min(left[i],right[i])−height[i]$

    • 初始化左右指针
    • 遍历数组（从1开始到n-1）
      • 计算left[i]，左指针从1开始，到n-1结束。因为0位置没有左柱子
      • 计算right[n-i-1]，右指针从n-2开始，到0结束。因为n-1位置没有右柱子
    • 遍历left，right，height。
      • 计算每个柱子的雨水量。min(left[i],right[i])-height[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        sum = 0
        #初始化左右指针，左指针为第一个位置的高，右指针为最后一个位置的高
        left = [height[0]]*n
        right = [height[-1]]*n
        #左指针从第二个位置开始到最后一个位置（因为初始化了第一个位置，要从第二个开始比较）
        #右指针从倒数第二个位置开始到第一个位置（因为倒数第一个位置没有右边的柱子）
        #每个指针都和其当前所指位置的高度比较，得出当前位置的左右边最高柱子的高度
        for i in range(1,n):
            left[i] = max(left[i-1],height[i])
            right[n-i-1] = max(right[n-i],height[n-i-1])
        #每个位置左右边最高柱子的高度-当前位置的高度=当前位置的雨水量
        for l,r,h in zip(left,right,height):
            sum += min(l,r)-h
        return sum

9. 找到字符串中所有字母异位词

  • 滑动窗口方法

    题目：给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

    异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

    分析：采用滑动窗口的模板（遍历右指针，左指针移动）

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
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        n, m = len(s), len(p)
        res = []
        if n<m:
            return []
        cnt = collections.Counter(p) # 字典，字符：数目。所需要的每个字符的数量
        need = m # 总的字符需要的数量
        for right in range(n):
            ch = s[right] # 右指针插入的字符
             #如果字符是所需要的，need-1且cnt[ch]-1
            if ch in cnt:
                if cnt[ch]>0:
                    need-=1
                cnt[ch]-=1
            # 因为窗口大小是固定的，因此需要根据右指针和m计算左指针位置
            left = right-m
            if left>=0:
                ch = s[left] # 左指针弹出的字符
                # 如果弹出的字符是所需要的字符，need+1且cnt[ch]+1
                if ch in cnt:
                    if cnt[ch]>=0:
                        need+=1
                    cnt[ch]+=1
            # 窗口包括了所需的字符，记录左指针位置
            if need==0:
                res.append(right-m+1) # 需要+1，因为left指针所指的位置是满足要求位置的前面一个位置
        return res

10. 最小覆盖子串

  • 滑动窗口方法

    题目：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

    分析：采用滑动窗口的模板（遍历右指针，左指针移动）

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
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(s)<len(t):
            return ""
        
        cnt = collections.Counter(t) # 字典，字符：数目。所需要的每个字符的数量
        need = len(t) # 总的字符需要的数量

        n=len(s)
        start,end = 0,-1
        min_len = n+1 # 初始化一个大的值
        left,right=0,0

        for right in range(n):
            ch = s[right] # 右指针插入的字符
            #如果字符是所需要的，need-1且cnt[ch]-1
            if ch in cnt:
                if cnt[ch]>0:
                    need-=1
                cnt[ch]-=1
            #当匹配了所有需要的字符后，移动左指针，找最小长度
            while need==0:
                if right-left+1<min_len:
                    min_len = right-left+1
                    start,end = left,right
                # 左指针弹出的字符
                ch = s[left]
                # 如果弹出的字符是所需要的字符，need+1且cnt[ch]+1
                if ch in cnt:
                    if cnt[ch]>=0:
                        need+=1
                    cnt[ch]+=1
                left+=1 # 移动左指针，缩小窗口长度
        return s[start:end+1] #因为左闭右开，记得右+1

11. 有效的括号

  • 栈方法

    题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

    有效字符串需满足：

    1. 左括号必须用相同类型的右括号闭合。
    2. 左括号必须以正确的顺序闭合。
    3. 每个右括号都有一个对应的相同类型的左括号。

    分析：栈的特点是先入后出，括号配对题目也满足先入后出特点（因为当出现右括号时，如果想要配对，栈顶的元素一定是与其对应的左括号，并且这个元素一定是距离当前右括号最近的左括号）。

    • 初始化字典（存储左右括号的配对，键为左括号，值为右括号）和栈（存储左括号）

    • 循环遍历字符串s。

      • 当s为左括号时入栈；
      • 当s为右括号时出栈，并比较出栈元素是否与左括号配对。不配对则返回False
    • 最终判断栈的长度是否为1，因为初始化栈时有一个元素’?’（便于判断第一个元素是右括号的情况，这种情况需要栈中有元素，否则无法出栈）

    注意：因为考虑到第一个字符就是右括号的情况，所以栈初始化时有一个元素，并且字典中也有它的配对。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def isValid(self, s: str) -> bool:
        dic = {'{':'}','(':')','[':']','?':'?'} #需要有'?‘的配对，因为右括号的情况下，需要'?'出栈
        stack = ['?'] #存储s中的左括号，初始有一个字符是为了解决第一个字符是右括号的情况
        #第一个字符是右括号，如果stack为空，无法pop
        for c in s:
            #如果c是左括号，放入到栈中
            if c in dic:
                stack.append(c)
            #如果c是右括号，出栈的左括号在dic中对应的值，是不是c
            elif dic[stack.pop()] !=c:
                return False
        #判断有没有多余的左括号在栈中
        return len(stack)==1