Python小白 Leetcode刷題歷程 No.76-No.80 最小覆蓋子串、組合、子集、單詞搜索、刪除排序數(shù)組中的重復(fù)項(xiàng)Ⅱ

寫在前面：

作為一個(gè)計(jì)算機(jī)院的大學(xué)生，總覺得僅僅在學(xué)校粗略的學(xué)習(xí)計(jì)算機(jī)專業(yè)課是不夠的，尤其是假期大量的空檔期，作為一個(gè)小白，實(shí)習(xí)也莫得路子，又不想白白耗費(fèi)時(shí)間。于是選擇了Leetcode這個(gè)平臺(tái)來刷題庫。編程我只學(xué)過基礎(chǔ)的C語言，現(xiàn)在在自學(xué)Python，所以用Python3.8刷題庫?，F(xiàn)在我Python掌握的還不是很熟練，算法什么的也還沒學(xué)，就先不考慮算法上的優(yōu)化了，單純以解題為目的，復(fù)雜程度什么的以后有時(shí)間再優(yōu)化。計(jì)劃順序五個(gè)題寫一篇日志，希望其他初學(xué)編程的人起到一些幫助，寫算是對(duì)自己學(xué)習(xí)歷程的一個(gè)見證了吧。

有一起刷LeetCode的可以關(guān)注我一下，我會(huì)一直發(fā)LeetCode題庫Python3解法的，也可以一起探討。

覺得有用的話可以點(diǎn)贊關(guān)注下哦，謝謝大家！
········································································································································································

No.76.最小覆蓋子串

難度：困難
題目描述：

在這里插入圖片描述

題解代碼（Python3.8）

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import Counter 
        t = Counter(t)
        res = ''
        n = 0       #當(dāng)前我滿足了 t 中的字母的種數(shù)
        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):    # 判斷當(dāng)前l(fā)eft處的字母是否必要
                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

或許有用的知識(shí)點(diǎn)：
這道題可能會(huì)用到python中的Counter函數(shù)，Counter函數(shù)的部分介紹如下：

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

這道題可以用到python的enumerat()函數(shù)，enumerate()函數(shù)的介紹如下：

在這里插入圖片描述

解題思路：
left和right是當(dāng)前目標(biāo)串的最左下標(biāo)和最右下標(biāo),right不斷向前進(jìn),left在保證當(dāng)前字母沒有必要保留時(shí)向前進(jìn)（沒有必要指：這個(gè)字母不在目標(biāo)字符串里,或者這個(gè)字母當(dāng)前數(shù)量已經(jīng)超過要求），這是一個(gè)貪心策略。t統(tǒng)計(jì)了目標(biāo)字母還需要多少,n 是 cnt 中的字母有幾種的數(shù)量已經(jīng)滿足了,res 則是最終的答案。知道了這些后看代碼結(jié)合代碼中的注釋就很容易理解了。

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

或許有用的知識(shí)點(diǎn)：
這道題要用到回溯算法。

解題思路：
這道題要返回所有滿足條件的集合，所以要用到回溯算法。套用回溯算法的模板，則回溯函數(shù)的三個(gè)組成部分分別為：
1.回溯出口：當(dāng)tmp的長度等于k時(shí)res.append(tmp)并返回。
2.回溯主體：對(duì)于for i in range(index,n+1)的所有值，都進(jìn)入下一個(gè)回溯狀態(tài)。
3.狀態(tài)返回：因?yàn)榛厮葜黧w沒有對(duì)全局變量做出什么改變，所以不需要狀態(tài)返回。

No.78.子集

難度：中等
題目描述：

在這里插入圖片描述

或許有用的知識(shí)點(diǎn)：
這道題要用到回溯算法。

解題思路：
這道題要返回所有可能的子集，所以要用到回溯算法。套用回溯算法的模板，則回溯函數(shù)的三個(gè)組成部分分別為：
1.回溯出口：這道題中所有解都是回溯出口，所以無需篩選，直接res.append(tmp)。
2.回溯主體：對(duì)于for i in range(index,l)的所有值，都進(jìn)入下一個(gè)回溯狀態(tài)。
3.狀態(tài)返回：因?yàn)樗薪舛际腔厮莩隹?，所以不需要狀態(tài)返回。

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

或許有用的知識(shí)點(diǎn)：
這道題要進(jìn)行試探和回溯，要使用回溯算法。

解題思路：
這道題要檢測相鄰單元格是否能連成所求單詞，需要確定一個(gè)起點(diǎn)，一步步試探、回溯，所以要用到回溯算法。套用回溯算法的模板，則回溯函數(shù)的三個(gè)組成部分分別為：
1.回溯出口：當(dāng)回溯的索引值達(dá)到單詞的最后一個(gè)單詞時(shí)，返回board[start_x][start_y] == word[index]
的布爾值。
2.回溯主體：如果board[start_x][start_y] == word[index]，對(duì)grid添加True標(biāo)記，將（start_x,start_y）增加direction，如果滿足（new_x,new_y）滿足問題要求的所有條件，那么進(jìn)入下一個(gè)狀態(tài)。
3.狀態(tài)返回：如果當(dāng)前狀態(tài)不滿足條件，那么取消對(duì)grid的True標(biāo)記。
在定義回溯函數(shù)前，我們還要定義一個(gè)m*n的布爾值二維數(shù)組，賦初值為全False，代表這個(gè)位置是否已經(jīng)使用過。

No.80.刪除排序數(shù)組中的重復(fù)項(xiàng)Ⅱ

難度：中等
題目描述：

在這里插入圖片描述

題解代碼（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

或許有用的知識(shí)點(diǎn)：
這道題可以使用雙指針法。

解題思路：
先記錄數(shù)組的長度之后倒序判斷，如果連續(xù)出現(xiàn)三個(gè)相同數(shù)，彈出這個(gè)數(shù)，數(shù)組長度減一。

優(yōu)解代碼及分析：
優(yōu)解代碼（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

分析：
這是用雙指針法的代碼，兩個(gè)指針?biāo)饕嗖?。