Python小白 Leetcode刷題歷程 No.56-No.60 合并區(qū)間狡门、插入?yún)^(qū)間、最后一個(gè)單詞的長(zhǎng)度锅很、螺旋矩陣Ⅱ其馏、第k個(gè)排列
寫(xiě)在前面：
作為一個(gè)計(jì)算機(jī)院的大學(xué)生，總覺(jué)得僅僅在學(xué)校粗略的學(xué)習(xí)計(jì)算機(jī)專業(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.56.合并區(qū)間
難度：中等
題目描述：
題解代碼（Python3.8）
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
l=len(intervals)
res=[]
if l==0:
return res
i=0
left=intervals[i][0]
right=intervals[i][1]
while i<l:
left=intervals[i][0]
right=intervals[i][1]
while i<l-1 and intervals[i+1][0]<=right:
i+=1
right=max(intervals[i][1],right)
res.append([left,right])
i+=1
return res
解題思路：
先按首位置進(jìn)行排序;接下來(lái),如何判斷兩個(gè)區(qū)間是否重疊呢?比如 a = [1,4],b = [2,3]坎藐。當(dāng) a[1] >= b[0] 說(shuō)明兩個(gè)區(qū)間有重疊.
但是如何把這個(gè)區(qū)間找出來(lái)呢?
左邊位置一定是確定为牍，就是 a[0]，而右邊位置是 max(a[1], b[1])岩馍。所以,我們就能找出整個(gè)區(qū)間為:[1,4]碉咆。
No.57.插入?yún)^(qū)間
難度：困難
題目描述：
題解代碼（Python3.8）
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
def merge(intervals):
intervals.sort()
l=len(intervals)
res=[]
i=0
left=intervals[i][0]
right=intervals[i][1]
while i<l:
left=intervals[i][0]
right=intervals[i][1]
while i<l-1 and intervals[i+1][0]<=right:
i+=1
right=max(intervals[i][1],right)
res.append([left,right])
i+=1
return res
intervals.append(newInterval)
return merge(intervals)
解題思路：
這道題一看難度是困難，實(shí)際上根上一題‘No.56.合并區(qū)間’一樣兼雄，這道題就是將一個(gè)區(qū)間添加進(jìn)intervals中吟逝，再合并空間（同上一題‘No.56.合并區(qū)間’操作一樣）。所以赦肋，我們首先要定義一個(gè)merge函數(shù)（同上一題‘No.56.合并區(qū)間’的主函數(shù)一樣）块攒，之后將新區(qū)間newInterval添加進(jìn)intervals中励稳，再調(diào)用merge函數(shù)即可。
No.58.最后一個(gè)單詞的長(zhǎng)度
難度：簡(jiǎn)單
題目描述：
題解代碼（Python3.8）
class Solution:
def lengthOfLastWord(self, s: str) -> int:
res=0
s=s.strip()
for i in range(len(s)-1,-1,-1):
if s[i]!=' ':
res +=1
else:
break
return res
或許有用的知識(shí)點(diǎn)：
這道題可以用到python中的strip()函數(shù)囱井，strip()函數(shù)用于移除字符串頭尾指定的字符（默認(rèn)為空格或換行符）或字符序列驹尼。（注意：該方法只能刪除開(kāi)頭或是結(jié)尾的字符，不能刪除中間部分的字符庞呕。）
解題思路：
這道題比較簡(jiǎn)單新翎，先使用strip()函數(shù)去掉字符串頭尾的空格，之和從后往前判斷字符串是否為空格即可住练。
No.59.螺旋矩陣Ⅱ
難度：中等
題目描述：
題解代碼（Python3.8）
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
matrix=[[0 for _ in range(n)] for _ in range(n)]
left,right,top,bottom = 0,n-1,0,n-1
num,num_max = 1,n*n
while num <= num_max:
for i in range(left,right+1): #頂端,從左到右(此處多一個(gè)數(shù))
matrix[top][i] = num
num += 1
for i in range(top+1,bottom+1): #右端,從上到下
matrix[i][right] = num
num += 1
for i in range(right-1,left-1,-1): #底端,從右到左
matrix[bottom][i] = num
num += 1
for i in range(bottom-1,top,-1): #左端,從下到上（此處少一個(gè)數(shù)）
matrix[i][left] = num
num += 1
left += 1
right -= 1
top += 1
bottom -=1
return matrix
或許有用的知識(shí)點(diǎn)：
matrix=[[0 for _ in range(n)] for _ in range(m)]可以創(chuàng)建一個(gè)m行n列的全0數(shù)組地啰。
解題思路：
這道題先創(chuàng)建一個(gè)空數(shù)組，再將數(shù)字依次遞增地按照順序一層一層填入數(shù)組即可讲逛。注意亏吝，填入數(shù)組的四個(gè)方位的長(zhǎng)度最好不要相等，否則當(dāng)最內(nèi)層只有一個(gè)元素時(shí)會(huì)發(fā)生錯(cuò)誤盏混，下面有一張圖展示了數(shù)組填數(shù)的方法蔚鸥。
No.60.第k個(gè)排列
難度：中等
題目描述：
題解代碼（Python3.8）
class Solution:
def getPermutation(self, n: int, k: int) -> str:
def backtrack(index,k):
if index == n:
return
cnt = factorial[n-1-index]
for i in range(1,n+1):
if used[i]:
continue
if cnt < k:
k -= cnt
continue
path.append(i)
used[i] = True
backtrack(index+1,k)
if n == 0:
return ''
used = [False for _ in range(n+1)]
path = []
factorial = [1 for _ in range(n+1)]
for i in range(2,n+1):
factorial[i] = factorial[i-1]*i
backtrack(0,k)
return ''.join([str(x) for x in path])
或許有用的知識(shí)點(diǎn)：
這道題要用到回溯算法。
used = [False for _ in range(n+1)]可以創(chuàng)建一個(gè)容量為n的布爾值型一維數(shù)組许赃。
這道題嚴(yán)格來(lái)說(shuō)并不是回溯算法止喷，但是需要用到回溯算法中的‘剪枝’操作，而且這道題只有一條分支是有效的混聊，因此回溯函數(shù)種不用設(shè)置‘狀態(tài)返回’環(huán)節(jié)弹谁。
解題思路：
這道題我開(kāi)始用暴力的方法嘗試了一下，發(fā)現(xiàn)會(huì)超時(shí)技羔。又發(fā)現(xiàn)這道題其實(shí)是個(gè)樹(shù)形結(jié)構(gòu)僵闯，而且只有一個(gè)葉是有效解，因此我們可以采用回溯算法來(lái)解決藤滥。又因?yàn)檫@道題只有一條分支是有效的，因此回溯函數(shù)種不用設(shè)置‘狀態(tài)返回’環(huán)節(jié)社裆。套用回溯算法的模板拙绊，則回溯算法的三個(gè)組成部分分別為：
1.回溯出口：索引位置等于n；
2.回溯主體：遍歷[0,n+1),如果用過(guò)數(shù)字了泳秀，就繼續(xù)标沪，如果if cnt < k，則 k -= cnt并continue嗜傅，當(dāng)?shù)谝淮蝐nt >=k,將i記錄進(jìn)path中金句，記錄用過(guò)數(shù)字了，并進(jìn)行下一輪的回溯backtrack(index+1,k)吕嘀。
3.狀態(tài)返回：本題不用設(shè)置违寞。
定義完回溯函數(shù)后贞瞒，我們還需要?jiǎng)?chuàng)建一個(gè)容量為n的布爾值型一維數(shù)組，以存儲(chǔ)數(shù)字i是否使用過(guò)趁曼；再創(chuàng)建一個(gè)容量為n的一維數(shù)組军浆，儲(chǔ)存[1,n+1)的階乘；之后引用回溯函數(shù)即可挡闰。
