Python小白 Leetcode刷題歷程 No.61-No.65 旋轉鏈表莽龟、不同路徑、不同路徑Ⅱ锨天、最小路徑和毯盈、有效數(shù)字
寫在前面:
作為一個計算機院的大學生,總覺得僅僅在學校粗略的學習計算機專業(yè)課是不夠的病袄,尤其是假期大量的空檔期搂赋,作為一個小白,實習也莫得路子益缠,又不想白白耗費時間脑奠。于是選擇了Leetcode這個平臺來刷題庫。編程我只學過基礎的C語言幅慌,現(xiàn)在在自學Python宋欺,所以用Python3.8刷題庫。現(xiàn)在我Python掌握的還不是很熟練,算法什么的也還沒學齿诞,就先不考慮算法上的優(yōu)化了酸休,單純以解題為目的,復雜程度什么的以后有時間再優(yōu)化祷杈。計劃順序五個題寫一篇日志雨席,希望其他初學編程的人起到一些幫助,寫算是對自己學習歷程的一個見證了吧吠式。
有一起刷LeetCode的可以關注我一下,我會一直發(fā)LeetCode題庫Python3解法的抽米,也可以一起探討特占。
覺得有用的話可以點贊關注下哦,謝謝大家云茸!
········································································································································································
題解框架:
1.題目是目,難度
2.題干,題目描述
3.題解代碼(Python3(不是Python,是Python3))
4.或許有用的知識點(不一定有)
5.解題思路
6.優(yōu)解代碼及分析(當我發(fā)現(xiàn)有比我寫的好很多的代碼和思路我就會寫在這里)
········································································································································································
No.61.旋轉鏈表
難度:中等
題目描述:
題解代碼(Python3.8)
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if (not head) or (not head.next) :
return None if not head else head
old_tail = head
n = 1
while old_tail.next:
old_tail = old_tail.next
n += 1
old_tail.next = head
new_tail = head
for i in range(n - k%n -1):
new_tail =new_tail.next
new_head =new_tail.next
new_tail.next = None
return new_head
或許有用的知識點:
這道題可以使用快慢指針的思想标捺。
解題思路:
鏈表中的點已經相連懊纳,一次旋轉操作意味著:先將鏈表閉合成環(huán),再找到相應的位置斷開這個環(huán),確定新的鏈表頭和鏈表尾亡容。所以嗤疯,我們首先找到舊的尾部并將其與鏈表頭相連old_tail.next = head,整個鏈表閉合成環(huán)闺兢,同時計算出鏈表的長度n茂缚;找到新的尾部,第 (n-k%n-1)個節(jié)點屋谭,新的鏈表頭是第(n-k%n)個節(jié)點脚囊;斷開環(huán) new_tail.next = None,并返回新的鏈表頭 new_head即可桐磁。
優(yōu)解代碼及分析:
優(yōu)解代碼(Python3.8)
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
# 下面有 if n==0 ...判斷了悔耘,所以開頭的判斷可以省略
#if not head or k<=0:
# return head
# 創(chuàng)建一個啞節(jié)點,快指針我擂,慢指針衬以,統(tǒng)計節(jié)點個數(shù)的cur
dummy = ListNode(-1)
cur,n,fast,low,dummy.next = head,0,dummy,dummy,head
# 統(tǒng)計鏈表個數(shù)
while cur:
cur,n = cur.next,n+1
# 邊界條件不要忘記處理了
if n==0 or k%n==0:
return head
# 還有一個邊界條件不要忘了,k可能大于n校摩,所以要取模
n = k%n
# 快指針先移動n步
while fast.next and n>0:
fast,n = fast.next,n-1
# 快指針泄鹏,慢指針一起移動,找到需要切割的點
while fast.next:
low,fast = low.next,fast.next
# 改變鏈表的指向關系秧耗,注意這里的步驟不要亂了
# 先讓fast節(jié)點指向head(也就是dummy.next)
# 再是head(也就是dummy.next)指向low的下一個節(jié)點
# 這兩步如果弄反了就會出現(xiàn)節(jié)點丟失了
# 最后不要忘記將low.next置空
fast.next,dummy.next,low.next = head,low.next,None
return dummy.next
分析;
雙指針法寫起來思路比較清楚备籽,代碼比較簡單,代碼中有著極詳細的注釋,應該比較容易理解车猬。
No.62.不同路徑
難度:中等
題目描述:
題解代碼(Python3.8)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
#第一行/第一列每個格都只有一種走法
dp = [[1]*n] + [[1]+[0]*(n-1) for _ in range(m-1)]
for i in range(1,m):
for j in range(1,n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
或許有用的知識點:
這道題要用到動態(tài)規(guī)劃的方法霉猛。
解題思路:
這道題可以使用動態(tài)規(guī)劃的方法,套用動態(tài)規(guī)劃的模板珠闰,對于這道題惜浅,假設dp[i][j]是從左上角到第i行第j列的方格有多少總走法,動態(tài)規(guī)劃的三要素分別為:
狀態(tài):第一行和第一列都只有一種走法伏嗜,其他格子走法=上面一格的走法+左邊一格的走法
狀態(tài)轉移方程:dp[i][j] = dp[i-1][j] + dp[i][j-1]
邊界條件: dp = [[1]n] + [[1]+[0](n-1) for _ in range(m-1)]
空間復雜度:O(n2)
優(yōu)解代碼及分析:
優(yōu)解代碼(Python3.8)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
cur = [1]*n
for i in range(1,m):
for j in range(1,n):
cur[j] += cur[j-1]
return cur[n-1]
分析:
其實也是動態(tài)規(guī)劃的思想坛悉,只不過將創(chuàng)建的空間減少了一個維度,空間復雜度O(n)承绸。
No.63.不同路徑Ⅱ
難度:中等
題目描述:
題解代碼(Python3.8)
class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
if (not obstacleGrid) or (not obstacleGrid[0]):
return 0
l_row = len(obstacleGrid)
l_col = len(obstacleGrid[0])
dp = [ [0]*l_col for _ in range(l_row)]
#首位置
dp[0][0] = 1 if obstacleGrid[0][0] != 1 else 0
if dp[0][0] == 0:
return 0
#第一行
for j in range(1,l_col):
if obstacleGrid[0][j] != 1:
dp[0][j] = dp[0][j-1]
#第一列
for i in range(1,l_row):
if obstacleGrid[i][0] != 1:
dp[i][0] = dp[i-1][0]
#剩余位置
for i in range(1,l_row):
for j in range(1,l_col):
if obstacleGrid[i][j] != 1:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[l_row-1][l_col-1]
或許有用的知識點:
這道題要用到動態(tài)規(guī)劃的方法裸影。
解題思路:
這道題根上一道題‘No.62.不同路徑’很相似,是上一題的加強版军熏。
這道題可以使用動態(tài)規(guī)劃的方法轩猩,套用動態(tài)規(guī)劃的模板,對于這道題荡澎,假設dp[i][j]是從左上角到第i行第j列的方格有多少總走法均践,動態(tài)規(guī)劃的三要素分別為:
狀態(tài):第一行和第一列都只有一種走法,其他格子走法=上面一格的走法+左邊一格的走法摩幔;但如果這一格有障礙物彤委,該格的dp=0。
狀態(tài)轉移方程:if obstacleGrid[i][j] != 1: dp[i][j] = dp[i-1][j] + dp[i][j-1]
邊界條件:
(#首位置)dp[0][0] = 1 if obstacleGrid[0][0] != 1 else 0 或衡;
(#第一行)if obstacleGrid[0][j] != 1: dp[0][j] = dp[0][j-1]葫慎;
(#第一列)if obstacleGrid[i][j] != 1: dp[i][j] = dp[i-1][j] + dp[i][j-1]。
No.64.最小路徑和
難度:中等
題目描述:
題解代碼(Python3.8)
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
if (not grid) or (not grid[0]):
return 0
m = len(grid)
n = len(grid[0])
dp = [[0]*n for _ in range(m)]
dp[0][0] = grid[0][0] #首位
for j in range(1,n): #第一行
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1,m): #第一列
dp[i][0] = dp[i-1][0] + grid[i][0]
for i in range(1,m):
for j in range(1,n):
dp[i][j] = min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j])
return dp[m-1][n-1]
或許有用的知識點:
這道題要用到動態(tài)規(guī)劃的方法薇宠。
解題思路:
這道題可以使用動態(tài)規(guī)劃的方法偷办,套用動態(tài)規(guī)劃的模板,對于這道題澄港,假設dp[i][j]是從左上角到第i行第j列的方格路徑的數(shù)字總和最小值椒涯,動態(tài)規(guī)劃的三要素分別為:
狀態(tài):第一行和第一列都只有一種走法,其他格子的路徑的數(shù)字總和最小值=(上面一格的路徑的數(shù)字總和最小值+第i行第j列的方格的數(shù)字) 和 (左邊一格的路徑的數(shù)字總和最小值+第i行第j列的方格的數(shù)字)二者之間的最小值回梧。
狀態(tài)轉移方程:dp[i][j] = min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j])
邊界條件:
(#首位置) dp[0][0] = grid[0][0] 废岂;
(#第一行)for j in range(1,n): dp[0][j] = dp[0][j-1] + grid[0][j];
(#第一列)for i in range(1,m): dp[i][0] = dp[i-1][0] + grid[i][0]狱意。
No.65.有效數(shù)字
難度:困難
題目描述:
題解代碼(Python3.8)
class Solution:
def isNumber(self, s: str) -> bool:
state = [
{},
# 狀態(tài)1,初始狀態(tài)(掃描通過的空格)
{"blank": 1, "sign": 2, "digit": 3, ".": 4},
# 狀態(tài)2,發(fā)現(xiàn)符號位(后面跟數(shù)字或者小數(shù)點)
{"digit": 3, ".": 4},
# 狀態(tài)3,數(shù)字(一直循環(huán)到非數(shù)字)
{"digit": 3, ".": 5, "e": 6, "blank": 9},
# 狀態(tài)4,小數(shù)點(后面只有緊接數(shù)字)
{"digit": 5},
# 狀態(tài)5,小數(shù)點之后(后面只能為數(shù)字,e,或者以空格結束)
{"digit": 5, "e": 6, "blank": 9},
# 狀態(tài)6,發(fā)現(xiàn)e(后面只能符號位, 和數(shù)字)
{"sign": 7, "digit": 8},
# 狀態(tài)7,e之后(只能為數(shù)字)
{"digit": 8},
# 狀態(tài)8,e之后的數(shù)字后面(只能為數(shù)字或者以空格結束)
{"digit": 8, "blank": 9},
# 狀態(tài)9, 終止狀態(tài) (如果發(fā)現(xiàn)非空,就失敗)
{"blank": 9}
]
cur_state = 1
for c in s:
if c.isdigit():
c = "digit"
elif c in " ":
c = "blank"
elif c in "+-":
c = "sign"
if c not in state[cur_state]:
return False
cur_state = state[cur_state][c]
if cur_state not in [3, 5, 8, 9]:
return False
return True
或許有用的知識點:
這道題要用到有限狀態(tài)機(FSM)湖苞,或者說有限狀態(tài)機的一種特殊狀態(tài)——有限自動機(DFA)的思想(在數(shù)字電路基礎、Verilog详囤、離散數(shù)學等大學專業(yè)課中應該學習過)财骨。
解題思路:
以下為一個考慮到各種情況的有限自動機模型镐作,狀態(tài)機的結構可以結合代碼中的注釋一起理解。(自己設計一個狀態(tài)機有時不能一開始就考慮到所有情況隆箩,要多測試不同情況)该贾。我們的代碼先創(chuàng)建一個state包含狀態(tài)機的所有狀態(tài)與內容,之和將字符串中的字符依次放入狀態(tài)機運行捌臊,最后查看狀態(tài)機的狀態(tài)是否在指定狀態(tài)即可杨蛋。