Python小白 Leetcode刷題歷程 No.76-No.80 最小覆蓋子串回梧、組合废岂、子集、單詞搜索狱意、刪除排序數組中的重復項Ⅱ
寫在前面：
作為一個計算機院的大學生湖苞，總覺得僅僅在學校粗略的學習計算機專業(yè)課是不夠的，尤其是假期大量的空檔期详囤，作為一個小白财骨，實習也莫得路子，又不想白白耗費時間藏姐。于是選擇了Leetcode這個平臺來刷題庫隆箩。編程我只學過基礎的C語言，現(xiàn)在在自學Python羔杨，所以用Python3.8刷題庫“齐現(xiàn)在我Python掌握的還不是很熟練，算法什么的也還沒學兜材，就先不考慮算法上的優(yōu)化了理澎，單純以解題為目的逞力，復雜程度什么的以后有時間再優(yōu)化。計劃順序五個題寫一篇日志糠爬，希望其他初學編程的人起到一些幫助寇荧，寫算是對自己學習歷程的一個見證了吧。
有一起刷LeetCode的可以關注我一下执隧，我會一直發(fā)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): # 判斷當前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
或許有用的知識點：
這道題可能會用到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統(tǒng)計了目標字母還需要多少,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)的所有值喘漏，都進入下一個回溯狀態(tài)护蝶。
3.狀態(tài)返回：因為回溯主體沒有對全局變量做出什么改變，所以不需要狀態(tài)返回翩迈。
No.78.子集
難度：中等
題目描述：
或許有用的知識點：
這道題要用到回溯算法持灰。
解題思路：
這道題要返回所有可能的子集，所以要用到回溯算法帽馋。套用回溯算法的模板搅方，則回溯函數的三個組成部分分別為：
1.回溯出口：這道題中所有解都是回溯出口比吭，所以無需篩選，直接res.append(tmp)姨涡。
2.回溯主體：對于for i in range(index,l)的所有值衩藤，都進入下一個回溯狀態(tài)。
3.狀態(tài)返回：因為所有解都是回溯出口涛漂，所以不需要狀態(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
或許有用的知識點：
這道題要進行試探和回溯，要使用回溯算法匈仗。
解題思路：
這道題要檢測相鄰單元格是否能連成所求單詞瓢剿，需要確定一個起點，一步步試探悠轩、回溯间狂，所以要用到回溯算法。套用回溯算法的模板火架，則回溯函數的三個組成部分分別為：
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）滿足問題要求的所有條件骡男，那么進入下一個狀態(tài)淆游。
3.狀態(tài)返回：如果當前狀態(tài)不滿足條件，那么取消對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
或許有用的知識點：
這道題可以使用雙指針法。
解題思路：
先記錄數組的長度之后倒序判斷来屠，如果連續(xù)出現(xiàn)三個相同數虑椎，彈出這個數，數組長度減一俱笛。
優(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
分析：
這是用雙指針法的代碼捆姜，兩個指針索引相差2。
