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