Python小白 Leetcode刷題歷程 No.36-No.40 有效的數(shù)獨搓茬、解數(shù)獨、外觀數(shù)列队他、組合總和卷仑、組合總和Ⅱ
寫在前面：
作為一個計算機院的大學(xué)生，總覺得僅僅在學(xué)校粗略的學(xué)習(xí)計算機專業(yè)課是不夠的麸折，尤其是假期大量的空檔期锡凝，作為一個小白，實習(xí)也莫得路子垢啼，又不想白白耗費時間窜锯。于是選擇了Leetcode這個平臺來刷題庫。編程我只學(xué)過基礎(chǔ)的C語言芭析，現(xiàn)在在自學(xué)Python锚扎，所以用Python3.8刷題庫。現(xiàn)在我Python掌握的還不是很熟練馁启，算法什么的也還沒學(xué)驾孔，就先不考慮算法上的優(yōu)化了芍秆，單純以解題為目的，復(fù)雜程度什么的以后有時間再優(yōu)化翠勉。計劃順序五個題寫一篇日志妖啥，希望其他初學(xué)編程的人起到一些幫助，寫算是對自己學(xué)習(xí)歷程的一個見證了吧对碌。
有一起刷LeetCode的可以關(guān)注我一下荆虱，我會一直發(fā)LeetCode題庫Python3解法的，也可以一起探討朽们。
覺得有用的話可以點贊關(guān)注下哦怀读，謝謝大家！
········································································································································································
No.36.有效的數(shù)獨
難度：中等
題目描述：
題解代碼（Python3.8）
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
set_box=set()
for i in range(9):
for j in range(9):
if board[i][j].isdigit():
row = 'row_'+str(i)+' ' + board[i][j]
col = 'col_'+str(j)+' ' + board[i][j]
small_square = 'row-col_'+str(i//3)+'-'+str(j//3)+' ' + board[i][j]
if row in set_box or col in set_box or small_square in set_box:
return False
set_box.update([row,col,small_square])
return True
或許有用的知識點：
set.add(key)可以在set中添加一個元素华坦，set.remove(key)可以在set中刪除一個元素愿吹。
如果想在set中一次性假如多個元素，可使用set.update([key1,key2,key3])惜姐。
解題思路：
在數(shù)獨9宮格中犁跪，每個數(shù)字必定帶有三個特性：行數(shù)、列數(shù)歹袁、小方塊位置坷衍。對于一個i行j列的元素n，我們不妨定義它的特性為,row=row_i n , col=col_j n , small_square=row-col_(i//3)-(j)//3 n条舔。對于每個數(shù)枫耳，我們將他的三個特性儲存到一個set中。當(dāng)新一個數(shù)字的三個特性都不在set中孟抗，我們便將其寫入set迁杨；如果新一個數(shù)字有特性已經(jīng)在set中了，不滿足條件凄硼，返回False铅协。
No.37.解數(shù)獨
難度：困難
題目描述：
題解代碼（Python3.8）
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
row = [set(range(1,10)) for _ in range(9)] #行剩余可用數(shù)字
col = [set(range(1,10)) for _ in range(9)] #列剩余可用數(shù)字
block = [set(range(1,10)) for _ in range(9)] #塊剩余可用數(shù)字
empty = [] #收集空白位置
for i in range(9):
for j in range(9):
if board[i][j] != '.':
val = int(board[i][j])
row[i].remove(val)
col[j].remove(val)
block[(i//3)*3+(j//3)].remove(val)
else:
empty.append((i,j))
def backtrack(iter_=0):
if iter_ == len(empty):
return True
i,j = empty[iter_]
block_index = (i//3)*3+(j//3)
for val in row[i] & col [j] & block[block_index]:
row[i].remove(val)
col[j].remove(val)
block[block_index].remove(val)
board[i][j] = str(val)
if backtrack(iter_+1):
return True
row[i].add(val)
col[j].add(val)
block[block_index].add(val)
return False
backtrack()
或許有用的知識點：
這道題需要使用回溯算法。
set( range(j) ) for _ in range(i),可以制作一個i行j列的set型二維數(shù)組摊沉，例如set( range(3)) for _ in range(4) = [ {0,1,2} , {0,1,2} , {0,1,2} , {0,1,2} ]狐史。
要求列表A，B说墨，C的公共元素骏全，應(yīng)使用 A & B & C ,(邏輯運算 and or not 只會返回運算的布爾值)。
解題思路：
先確定回溯函數(shù)尼斧，對比回溯函數(shù)模板姜贡，回溯出口為iter_長度與empty相等，回溯主體中在當(dāng)發(fā)現(xiàn)子狀態(tài)的有效解后進入下一狀態(tài)棺棵，否則回溯到原來狀態(tài)鲁豪。
之后初始化狀態(tài)潘悼，要有行剩余可用數(shù)字、列剩余可用數(shù)字爬橡、塊剩余可用數(shù)字、空白方格位置棒动。最后調(diào)用回溯函數(shù)即可糙申。
No.38.外觀數(shù)列
難度：簡單
題目描述：
題解代碼（Python3.8）
class Solution:
def countAndSay(self, n: int) -> str:
prev_person = '1'
for i in range(1,n):
next_person,num,count = '',prev_person[0],1
for j in range(1,len(prev_person)):
if prev_person[j] == num:
count +=1
else:
next_person += str(count)+num
num = prev_person[j]
count =1
next_person += str(count)+num
prev_person = next_person
return prev_person
解題思路：
這個題就是題比較難讀懂，我翻譯了一下船惨，其實就是：
1.1
2.描述的是1柜裸，是一個1，也就是11
3.描述的是11粱锐，是兩個1疙挺，也就是21
- 描述的是21，是一個2一個1怜浅，也就是12-11
- 描述的是1211, 是一個1铐然，一個2，兩個1恶座，也就是11-12-21
- 描述的是111221搀暑，是三個1，兩個2跨琳，一個1自点，也就是31-22-11
- 描述的是312211，是一個3一個1兩個2兩個1脉让，也即是13-11-22-21
以此類推
所以對字符串進行一次遍歷就好桂敛，將已生成的最后一個數(shù)稱為‘上一個數(shù)’，再通過‘上一個數(shù)’推出‘下一個數(shù)’溅潜，然后把‘下一個數(shù)’的值賦給上一個數(shù)术唬，繼續(xù)遍歷即可。
No.39.組合總和
難度：中等
題目描述：
題解代碼（Python3.8）
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
l=len(candidates)
if l==0:
return []
candidates.sort()
path=[]
res=[]
def backtrack(begin,path,target):
if target==0:
res.append(path[:])
for i in range(begin,l):
target_next=target-candidates[i] #剪枝操作
if target_next<0:
break
path.append(candidates[i])
backtrack(i,path,target_next)
path.pop()
backtrack(0,path,target)
return res
或許有用的知識點：
這道題要用到回溯算法伟恶。
a=p與a=p[:]的區(qū)別：a=p是把p的地址給a碴开，p和a指向同一對象；而a=p[:]是創(chuàng)建一個內(nèi)容與p全等的對象博秫，命名為a潦牛，a指向p的副本，p和a指向不同對象挡育。再回溯算法中巴碗，對可能被回溯的待保存元素，有時需要以a=p[:] 的方式儲存即寒。
解題思路：
定義回溯函數(shù)橡淆，在減的過程中召噩，得到 0或者負(fù)數(shù)，就沒有必要再走下去逸爵，所以這兩種情況就分別表示成為葉子結(jié)點具滴。此時遞歸結(jié)束，然后要發(fā)生回溯师倔。注意构韵，這道題中組合里的數(shù)字可以無限制重復(fù)被選取。而要想完成剪枝趋艘，前提是數(shù)組是有序的疲恢，因此我們需要對數(shù)組進行排序。注意瓷胧，Python 中可變對象是引用傳遞显拳，因此需要將當(dāng)前 path 里的值拷貝出來，即a=p[:]搓萧。
No.40.組合總和Ⅱ
難度：中等
題目描述：
題解代碼（Python3.8）
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
l=len(candidates)
if l==0:
return []
candidates.sort() #初始化
path=[]
res=[]
def backtrack(begin,path,target):
if target==0: #回溯出口
res.append(path[:])
for i in range(begin,l): #回溯主體
target_next=target-candidates[i] #剪枝操作
if target_next<0:
break
if i>begin and candidates[i-1]==candidates[i]:
continue
path.append(candidates[i])
backtrack(i+1,path,target_next)
path.pop() #狀態(tài)返回
backtrack(0,path,target)
return res
或許有用的知識點：
這道題要用到回溯算法杂数。
a=p與a=p[:]的區(qū)別：a=p是把p的地址給a，p和a指向同一對象矛绘；而a=p[:]是創(chuàng)建一個內(nèi)容與p全等的對象耍休，命名為a，a指向p的副本货矮，p和a指向不同對象羊精。再回溯算法中，對可能被回溯的待保存元素囚玫，有時需要以a=p[:] 的方式儲存喧锦。
解題思路：
這道題跟‘39.組合總和’的思路類似，都是定義回溯函數(shù)抓督，與其差別就是這道題組合中每個數(shù)只能用使用一次燃少。在減的過程中，得到 0或者負(fù)數(shù)铃在，就沒有必要再走下去阵具，所以這兩種情況就分別表示成為葉子結(jié)點。此時遞歸結(jié)束定铜，然后要發(fā)生回溯阳液。要想完成剪枝，前提是數(shù)組是有序的揣炕，因此我們需要對數(shù)組進行排序帘皿。注意，Python 中可變對象是引用傳遞畸陡，因此需要將當(dāng)前 path 里的值拷貝出來鹰溜，即a=p[:]虽填。
