Python小白 Leetcode刷题历程 No.76-No.80 最小覆盖子串、组合、子集、单词搜索、删除排序数组中的重复项Ⅱ

写在前面：

作为一个计算机院的大学生，总觉得仅仅在学校粗略的学习计算机专业课是不够的，尤其是假期大量的空档期，作为一个小白，实习也莫得路子，又不想白白耗费时间。于是选择了Leetcode这个平台来刷题库。编程我只学过基础的C语言，现在在自学Python，所以用Python3.8刷题库。现在我Python掌握的还不是很熟练，算法什么的也还没学，就先不考虑算法上的优化了，单纯以解题为目的，复杂程度什么的以后有时间再优化。计划顺序五个题写一篇日志，希望其他初学编程的人起到一些帮助，写算是对自己学习历程的一个见证了吧。

有一起刷LeetCode的可以关注我一下，我会一直发LeetCode题库Python3解法的，也可以一起探讨。

觉得有用的话可以点赞关注下哦，谢谢大家！
········································································································································································

No.76.最小覆盖子串

难度：困难
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import Counter 
        t = Counter(t)
        res = ''
        n = 0       #当前我满足了 t 中的字母的种数
        left = 0
        for right, char in enumerate(s):
            if char not in t: 
                continue
            t[char] -= 1
            if t[char] == 0:
                n += 1
            while (s[left] not in t) or (t[s[left]] < 0):    # 判断当前left处的字母是否必要
                if s[left] in t: 
                    t[s[left]] += 1
                left += 1
            if n == len(t):
                if (not res) or (len(res) > right-left+1):
                    res = s[left: right+1]
        return res

或许有用的知识点：
这道题可能会用到python中的Counter函数，Counter函数的部分介绍如下：

在这里插入图片描述
调用Counter函数需要调用头文件’from collections import Counter’
将一个list，tuple，dict，字符串等转化成Counter形式，将会输出dict中key : value形式，其中key为元素，value为该元素的个数。
Counter是无序性的，很适合做本题，Counter[key]=(相对应)value，如下图：
在这里插入图片描述
在这里插入图片描述

这道题可以用到python的enumerat()函数，enumerate()函数的介绍如下：

在这里插入图片描述

解题思路：
left和right是当前目标串的最左下标和最右下标,right不断向前进,left在保证当前字母没有必要保留时向前进（没有必要指：这个字母不在目标字符串里,或者这个字母当前数量已经超过要求），这是一个贪心策略。t统计了目标字母还需要多少,n 是 cnt 中的字母有几种的数量已经满足了,res 则是最终的答案。知道了这些后看代码结合代码中的注释就很容易理解了。

No.77.组合

难度：中等
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        if n <= 0 or k <= 0 or k > n:
            return []
        res = []
       
        def backtrack(index,tmp):
            if len(tmp) == k:
                res.append(tmp)
                return
            for i in range(index,n+1):
                backtrack(i+1,tmp+[i])
        
        backtrack(1,[])
        return res

或许有用的知识点：
这道题要用到回溯算法。

解题思路：
这道题要返回所有满足条件的集合，所以要用到回溯算法。套用回溯算法的模板，则回溯函数的三个组成部分分别为：
1.回溯出口：当tmp的长度等于k时res.append(tmp)并返回。
2.回溯主体：对于for i in range(index,n+1)的所有值，都进入下一个回溯状态。
3.状态返回：因为回溯主体没有对全局变量做出什么改变，所以不需要状态返回。

No.78.子集

难度：中等
题目描述：

在这里插入图片描述

或许有用的知识点：
这道题要用到回溯算法。

解题思路：
这道题要返回所有可能的子集，所以要用到回溯算法。套用回溯算法的模板，则回溯函数的三个组成部分分别为：
1.回溯出口：这道题中所有解都是回溯出口，所以无需筛选，直接res.append(tmp)。
2.回溯主体：对于for i in range(index,l)的所有值，都进入下一个回溯状态。
3.状态返回：因为所有解都是回溯出口，所以不需要状态返回。

No.79.单词搜索

难度：中等
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]
        m = len(board)
        n = len(board[0])
        if m == 0:
            return False
        grid = [[False for _ in range(n)] for _ in range(m)]
        
        def backtrack(index,start_x,start_y):
            if index == len(word)-1:
                return board[start_x][start_y] == word[index]
            if board[start_x][start_y] == word[index]:
                grid[start_x][start_y] = True
                for direction in directions:
                    new_x = start_x + direction[0]
                    new_y = start_y + direction[1]
                    if  0<=new_x<m and 0<=new_y<n and (not grid[new_x][new_y]) and backtrack(index+1,new_x,new_y):
                        return True
                grid[start_x][start_y] = False
            return False
      
        for i in range(m):
            for j in range(n):
                if backtrack(0,i,j):
                    return True
        return False

或许有用的知识点：
这道题要进行试探和回溯，要使用回溯算法。

解题思路：
这道题要检测相邻单元格是否能连成所求单词，需要确定一个起点，一步步试探、回溯，所以要用到回溯算法。套用回溯算法的模板，则回溯函数的三个组成部分分别为：
1.回溯出口：当回溯的索引值达到单词的最后一个单词时，返回board[start_x][start_y] == word[index]
的布尔值。
2.回溯主体：如果board[start_x][start_y] == word[index]，对grid添加True标记，将（start_x,start_y）增加direction，如果满足（new_x,new_y）满足问题要求的所有条件，那么进入下一个状态。
3.状态返回：如果当前状态不满足条件，那么取消对grid的True标记。
在定义回溯函数前，我们还要定义一个m*n的布尔值二维数组，赋初值为全False，代表这个位置是否已经使用过。

No.80.删除排序数组中的重复项Ⅱ

难度：中等
题目描述：

在这里插入图片描述

题解代码（Python3.8）

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        l = len(nums)
        for i in range(l-3,-1,-1):
            if nums[i] == nums[i+1] == nums[i+2]:
                nums.pop(i)
                l -= 1
        return l

或许有用的知识点：
这道题可以使用双指针法。

解题思路：
先记录数组的长度之后倒序判断，如果连续出现三个相同数，弹出这个数，数组长度减一。

优解代码及分析：
优解代码（Python3.8）

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        start, end = 0, 0     
        while end < len(nums):
            if start<2 or nums[end] != nums[start-2]:
                nums[start] = nums[end];
                start+=1
            end+=1
        return start

分析：
这是用双指针法的代码，两个指针索引相差2。