Python小白 Leetcode刷題歷程 No.51-No.55 N皇后棵逊、N皇后Ⅱ、最大子序和银酗、螺旋矩陣辆影、跳躍游戲
寫(xiě)在前面：
作為一個(gè)計(jì)算機(jī)院的大學(xué)生，總覺(jué)得僅僅在學(xué)校粗略的學(xué)習(xí)計(jì)算機(jī)專(zhuān)業(yè)課是不夠的黍特，尤其是假期大量的空檔期蛙讥，作為一個(gè)小白，實(shí)習(xí)也莫得路子灭衷，又不想白白耗費(fèi)時(shí)間次慢。于是選擇了Leetcode這個(gè)平臺(tái)來(lái)刷題庫(kù)。編程我只學(xué)過(guò)基礎(chǔ)的C語(yǔ)言，現(xiàn)在在自學(xué)Python迫像，所以用Python3.8刷題庫(kù)∈锰В現(xiàn)在我Python掌握的還不是很熟練，算法什么的也還沒(méi)學(xué)侵蒙，就先不考慮算法上的優(yōu)化了造虎，單純以解題為目的，復(fù)雜程度什么的以后有時(shí)間再優(yōu)化纷闺。計(jì)劃順序五個(gè)題寫(xiě)一篇日志算凿，希望其他初學(xué)編程的人起到一些幫助，寫(xiě)算是對(duì)自己學(xué)習(xí)歷程的一個(gè)見(jiàn)證了吧犁功。
有一起刷LeetCode的可以關(guān)注我一下氓轰，我會(huì)一直發(fā)LeetCode題庫(kù)Python3解法的，也可以一起探討浸卦。
覺(jué)得有用的話可以點(diǎn)贊關(guān)注下哦署鸡，謝謝大家！
········································································································································································
題解框架：
1.題目限嫌，難度
2.題干,題目描述
3.題解代碼（Python3（不是Python靴庆，是Python3））
4.或許有用的知識(shí)點(diǎn)（不一定有）
5.解題思路
6.優(yōu)解代碼及分析（當(dāng)我發(fā)現(xiàn)有比我寫(xiě)的好很多的代碼和思路我就會(huì)寫(xiě)在這里）
········································································································································································
No.51.N皇后
難度：困難
題目描述：
題解代碼（Python3.8）
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res=[]
if n == 0:
return res
nums = [ i for i in range(n)]
col = set()
master = set()
slave = set()
stack = []
def backtrack(row):
if row == n:
board = solution(stack,n)
res.append(board)
return
for i in range(n):
if (i not in col) and (row+i not in master) and (row-i not in slave):
stack.append(nums[i])
col.add(i)
master.add(row+i)
slave.add(row-i)
backtrack(row+1)
stack.pop()
col.remove(i)
master.remove(row+i)
slave.remove(row-i)
def solution(stack,n):
return ['.'*stack[i] + 'Q' + '.'*(n-stack[i]-1) for i in range(n)]
backtrack(0)
return res
或許有用的知識(shí)點(diǎn)：
這道題要用到回溯算法。
解題思路：
這道題是樹(shù)形結(jié)構(gòu)怒医，且需要剪枝炉抒，于是我們采用回溯算法。按照回溯算法的模板稚叹，本題我們將行(row)作為回溯函數(shù)的變量焰薄，套用回溯算法的模板，則回溯算法的三個(gè)組成部分分別為：
1.回溯出口：行數(shù)row==n扒袖，將該情況的解法儲(chǔ)存進(jìn)結(jié)果res中塞茅；
2.回溯主體：如果對(duì)于該行的列位置i，如果i滿足無(wú)列沖突（因?yàn)槭侵鹦谢厮菁韭剩虼吮囟ú粫?huì)行沖突）野瘦、無(wú)斜線沖突（橫縱坐標(biāo)之和之差都不沖突），則記錄該位置的行（記錄兩次蚀同，一個(gè)是列表形式為了生成解缅刽，另一個(gè)是set形式為了判斷是否沖突）啊掏、橫縱坐標(biāo)和蠢络、橫縱坐標(biāo)差，之和執(zhí)行回溯函數(shù)backtrack(row+1);
3.狀態(tài)返回：說(shuō)明已經(jīng)結(jié)束了該分支的回溯迟蜜，則刪除剛才記錄的該位置的行刹孔、橫縱坐標(biāo)和、橫縱坐標(biāo)差。
為滿足回溯函數(shù)髓霞，我們考慮創(chuàng)建一個(gè)從1到n的n元素的列表卦睹，和列、橫縱坐標(biāo)和方库、橫縱坐標(biāo)差的空set结序，來(lái)判斷是否沖突；我們用一個(gè)列表纵潦，儲(chǔ)存皇后在每一行的列位置徐鹤，最后定義一個(gè)函數(shù)，將這個(gè)列表轉(zhuǎn)換成棋盤(pán)格式的解邀层，最后返回res即可返敬。
No.52.N皇后Ⅱ
難度：困難
題目描述：
題解代碼（Python3.8）
class Solution:
def totalNQueens(self, n: int) -> int:
res=[]
if n == 0:
return res
col = set()
master = set()
slave = set()
def backtrack(row):
if row == n:
res.append('count')
return
for i in range(n):
if (i not in col) and (row+i not in master) and (row-i not in slave):
col.add(i)
master.add(row+i)
slave.add(row-i)
backtrack(row+1)
col.remove(i)
master.remove(row+i)
slave.remove(row-i)
backtrack(0)
return len(res)
或許有用的知識(shí)點(diǎn)：
這道題要用到回溯算法。
解題思路：
這道題的思路其實(shí)和上一題‘No.51.N皇后’基本一致寥院，而且這道題比上一題‘No.51.N皇后’簡(jiǎn)單劲赠，即閹割版；上一題‘No.51.N皇后’需要我們寫(xiě)出所有解法的內(nèi)容秸谢，本題只需寫(xiě)出解的數(shù)量即可凛澎。
這道題是樹(shù)形結(jié)構(gòu)，且需要剪枝估蹄，于是我們采用回溯算法预厌。按照回溯算法的模板，本題我們將行(row)作為回溯函數(shù)的變量元媚，則回溯算法的三個(gè)組成部分分別為：
1.回溯出口：行數(shù)row==n轧叽，將解的個(gè)數(shù)res+=1；
2.回溯主體：如果對(duì)于該行的列位置i刊棕，如果i滿足無(wú)列沖突（因?yàn)槭侵鹦谢厮萏可梗虼吮囟ú粫?huì)行沖突）、無(wú)斜線沖突（橫縱坐標(biāo)之和之差都不沖突）甥角，則記錄該位置的行网严、橫縱坐標(biāo)和、橫縱坐標(biāo)差嗤无，之和執(zhí)行回溯函數(shù)backtrack(row+1);
3.狀態(tài)返回：說(shuō)明已經(jīng)結(jié)束了該分支的回溯震束，則刪除剛才記錄的該位置的行、橫縱坐標(biāo)和当犯、橫縱坐標(biāo)差垢村。
為滿足回溯函數(shù)，我們考慮創(chuàng)建列嚎卫、橫縱坐標(biāo)和嘉栓、橫縱坐標(biāo)差的空set，來(lái)判斷是否沖突，并初始化res=0侵佃，最后返回res麻昼。
No.53.最大子序和
難度：簡(jiǎn)單
題目描述：
題解代碼（Python3.8）
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
l=len(nums)
if l==0:
return 0
dp=[0 for _ in range(l)]
dp[0]=nums[0]
for i in range(1,l):
dp[i] = max(dp[i-1]+nums[i],nums[i])
return max(dp)
或許有用的知識(shí)點(diǎn)：
這道題可用使用動(dòng)態(tài)規(guī)劃的方法。
這道題可用使用分治算法來(lái)解決（更為精妙馋辈，我會(huì)在‘優(yōu)解代碼及分析’詳細(xì)說(shuō)明）抚芦。
解題思路：
這道題是求最優(yōu)化解的問(wèn)題，且滿足動(dòng)態(tài)規(guī)劃問(wèn)題的條件迈螟，于是我們用動(dòng)態(tài)規(guī)劃的方法來(lái)做燕垃。這道題套用動(dòng)態(tài)規(guī)劃的模板，的到動(dòng)態(tài)規(guī)劃的三要素分別為：
狀態(tài)：從頭到第i個(gè)元素井联，能得到的最大子序和為dp[i]卜壕；則從頭到第i+1個(gè)元素，能得到的最大子序和為的(dp[i]+nums[i+1])和(nums[i+1])中的最大數(shù)值烙常。
狀態(tài)轉(zhuǎn)移方程：dp[i] = max(dp[i-1]+nums[i],nums[i])
邊界條件：dp[0]=nums[0]
之后對(duì)列表從頭到尾動(dòng)態(tài)規(guī)劃即可轴捎。
復(fù)雜度：
時(shí)間復(fù)雜度： O（N）
空間復(fù)雜度： O（1）
優(yōu)解代碼及分析：
優(yōu)解代碼（Python3.8）
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
l=len(nums)
if l <= 1:
return 0 if l==0 else nums[0]
else:
#遞歸計(jì)算左半邊最大子序和
max_left = self.maxSubArray(nums[0:l//2])
#遞歸計(jì)算右半邊最大子序和
max_right = self.maxSubArray(nums[l//2:l])
#計(jì)算中間的最大子序和，從右到左計(jì)算左邊的最大子序和蚕脏，從左到右計(jì)算右邊的最大子序和侦副，再相加
max_l = nums[l//2 -1]
tmp = 0
for i in range(l//2 -1,-1,-1):
tmp += nums[i]
max_l = max(tmp, max_l)
max_r = nums[l//2]
tmp = 0
for i in range(l//2,l):
tmp += nums[i]
max_r = max(tmp, max_r)
#返回三個(gè)中的最大值
return max(max_right,max_left,max_l+max_r)
分析：
官方說(shuō)分治法更為精美，其實(shí)......驼鞭，這道題里分治法比動(dòng)態(tài)規(guī)劃效率低秦驯。代碼中有一些注釋?zhuān)旅嬗幸粡垐D詳細(xì)舉例了這道題分治的過(guò)程。
復(fù)雜度：
時(shí)間復(fù)雜度： O（N*logN）
空間復(fù)雜度： O（1）
No.54.螺旋矩陣
難度：中等
題目描述：
題解代碼（Python3.8）
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix:
return []
L_row = len(matrix)
L_col = len(matrix[0])
def spiral(depth):
l_row,l_col = L_row-2*depth,L_col-2*depth
if l_row<=0 or l_col<=0:
return []
if l_row==1:
return matrix[depth][depth:depth+l_col]
if l_col==1:
return [ matrix[i][depth] for i in range(depth,depth+l_row) ]
res = []
res += matrix[depth][depth:depth+l_col]
res += [ matrix[i][depth+l_col-1] for i in range(depth+1,depth+l_row-1) ]
res += reversed(matrix[depth+l_row-1][depth:depth+l_col])
res += reversed([ matrix[i][depth] for i in range(depth+1,depth+l_row-1) ])
return res + spiral(depth+1)
return spiral(0)
或許有用的知識(shí)點(diǎn)：
可以了解一下Python中的reverse()函數(shù)和reversed(),一般用于反轉(zhuǎn)python中大多類(lèi)型的數(shù)據(jù)挣棕，下面是這兩個(gè)函數(shù)的一些介紹：
解題思路：
設(shè)置一個(gè)空列表res译隘，定義一個(gè)遞歸函數(shù)spiral，從外到內(nèi)一層一層記錄二維數(shù)組的值并遞歸到下一層即可洛心，最后輸出res固耘，代碼非常好理解。
No.55.跳躍游戲
難度：中等
題目描述：
題解代碼（Python3.8）
class Solution:
def canJump(self, nums: List[int]) -> bool:
max_jump=0
l=len(nums)
for i in range(l):
max_jump = max(max_jump,i+nums[i])
if max_jump>=l-1:
return True
if max_jump<i+1:
break
return False
或許有用的知識(shí)點(diǎn)：
這道題可以用到貪心算法词身。
解題思路：
總思路：如果最大跳躍距離大于等于最后一個(gè)位置的索引厅目，就表示能夠到達(dá)最后一個(gè)位置，反之則不能法严。
貪心算法：
定義能達(dá)到的最遠(yuǎn)位置max_jump=0损敷，遍歷數(shù)組，遍歷范圍[0,n-1)深啤；
所能達(dá)到的最遠(yuǎn)位置max_jump=max(max_jump,nums[i]+i)拗馒，表示上一最遠(yuǎn)位置和當(dāng)前索引i和索引i上的步數(shù)之和中的較大者。
如果max_jump大于等于最后一個(gè)位置的索引,就return True墓塌。
注意：數(shù)組遍歷范圍為[0,n-1)瘟忱。
復(fù)雜度分析
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)
其實(shí)這道題和‘No.45.跳躍游戲Ⅱ’思路很相似，‘No.45.跳躍游戲Ⅱ’是這道題的升級(jí)版苫幢，大家可以做一下這道題練習(xí)一下访诱。
No.45.跳躍游戲Ⅱ：
https://blog.csdn.net/LanXiu_/article/details/104177349
