Python小白 Leetcode刷題歷程 No.16-No.20 最接近的三數(shù)之和、Phone Number的字母組合、四數(shù)之和、刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)、有效的括號(hào)
寫在前面：
作為一個(gè)計(jì)算機(jī)院的大學(xué)生，總覺得僅僅在學(xué)校粗略的學(xué)習(xí)計(jì)算機(jī)專業(yè)課是不夠的，尤其是假期大量的空檔期，作為一個(gè)小白，實(shí)習(xí)也莫得路子，又不想白白耗費(fèi)時(shí)間。于是選擇了Leetcode這個(gè)平臺(tái)來刷題庫。編程我只學(xué)過基礎(chǔ)的C語言，現(xiàn)在在自學(xué)Python，所以用Python3.8刷題庫。現(xiàn)在我Python掌握的還不是很熟練，算法什么的也還沒學(xué)，就先不考慮算法上的優(yōu)化了，單純以解題為目的，復(fù)雜程度什么的以后有時(shí)間再優(yōu)化。計(jì)劃順序五個(gè)題寫一篇日志，希望其他初學(xué)編程的人起到一些幫助，寫算是對(duì)自己學(xué)習(xí)歷程的一個(gè)見證了吧。
有一起刷LeetCode的可以關(guān)注我一下，我會(huì)一直發(fā)LeetCode題庫Python3解法的，也可以一起探討。
覺得有用的話可以點(diǎn)贊關(guān)注下哦，謝謝大家！
········································································································································································
題解框架：
1.題目，難度
2.題干,題目描述
3.題解代碼（Python3（不是Python，是Python3））
4.或許有用的知識(shí)點(diǎn)（不一定有）
5.解題思路
6.優(yōu)解代碼及分析（當(dāng)我發(fā)現(xiàn)有比我寫的好很多的代碼和思路我就會(huì)寫在這里）
········································································································································································
No.16.最接近的三數(shù)之和
難度:中等
題目描述：
題解代碼（Python3.8）
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
res=nums[0]+nums[1]+nums[2]
d=abs(res-target)
l=len(nums)
for i in range(l-2):
L=i+1
R=l-1
while L<R:
if abs(nums[i]+nums[L]+nums[R]-target)<d:
res=nums[i]+nums[L]+nums[R]
d=abs(res-target)
if (nums[i]+nums[L]+nums[R])==target:
return res
elif nums[i]+nums[L]+nums[R]>target:
R -=1
else:
L +=1
return res
或許有用的知識(shí)點(diǎn)：
abs(x)=x的絕對(duì)值。
解題思路：
第十五題‘No.15.三數(shù)之和’思路類似，從一個(gè)數(shù)組中確定三個(gè)數(shù)，可以先for循環(huán)確定一個(gè)數(shù)，再用雙指針法確定后兩個(gè)數(shù)，然后判斷，根據(jù)判斷結(jié)果移動(dòng)指針直到不滿足L<R。
No.17.電話號(hào)碼的字母組合
難度：中等
題目描述：
題解代碼（Python3.8）
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
phone={'2':['a','b','c'],'3':['d','e','f'],'4':['g','h','i'],'5':['j','k','l'],
'6':['m','n','o'],'7':['p','q','r','s'],'8':['t','u','v'],'9':['w','x','y','z']}
def backtrack(combination,next_digits):
if len(next_digits)==0:
output.append(combination)
else:
for letter in phone[next_digits[0]]:
backtrack(combination+letter,next_digits[1:])
output=[]
if digits:
backtrack("",digits)
return output
或許有用的知識(shí)點(diǎn)：
回溯算法，在樹形結(jié)構(gòu)中找全部的解，通常使用回溯算法。
解題思路：
對(duì)與“23”我們不難推斷出它的解為下圖：
這顯然是在樹形結(jié)構(gòu)求樹葉的全部解，在樹形結(jié)構(gòu)中找全部的解，通常使用回溯算法。
先寫出這個(gè)題的字典，phone={‘?dāng)?shù)字（key）’：‘對(duì)應(yīng)字母（value）’}，然后定義回溯函數(shù)運(yùn)算即可，當(dāng)剩余數(shù)字長度為0，結(jié)束循環(huán)，否則，for遍歷這個(gè)數(shù)字的所有字母值，在每個(gè)循環(huán)中再次進(jìn)行回溯函數(shù)。
No.18.四數(shù)之和
難度：中等
題目描述：
題解代碼（Python3.8）
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
l=len(nums) #特解
if l<4:
return []
res=[]
nums.sort()
for i in range(l-2):
if nums[i]>(target/4)+1: #最小數(shù)>target/4，跳出循環(huán)
break
if i>0 and nums[i]==nums[i-1]: #最小數(shù)與上一輪循環(huán)相同，防止重復(fù)解，跳過
continue
for j in range(l)[::-1]:
if nums[j]<(target/4)-1: #最大數(shù)<target/4，跳出循環(huán)
break
if j<l-1 and nums[j]==nums[j+1]: #最大數(shù)與上一輪循環(huán)相同，防止重復(fù)解，跳過
continue
L=i+1
R=j-1
while L<R:
if nums[i]+nums[L]+nums[R]+nums[j] == target:
res.append([nums[i],nums[L],nums[R],nums[j]])
while L<R and nums[L]==nums[L+1]: #左指針向右跳過重復(fù)值，防止重復(fù)解
L +=1
while L<R and nums[R]==nums[R-1]: #右指針向左跳過重復(fù)值，防止重復(fù)解
R -=1
L +=1
R -=1
elif nums[i]+nums[L]+nums[R]+nums[j] > target: #四數(shù)和>0，右指針大了，左移
R -=1
else: #四數(shù)和<0，左指針小了，右移
L +=1
return res
解題思路：
這題跟例題第十五題‘No.15.三數(shù)之和’基本一致，只不過多了個(gè)數(shù)，我們可以確定一個(gè)最大數(shù)和一個(gè)最小數(shù)，中間兩數(shù)用雙指針。這道題我代碼中的標(biāo)注很詳細(xì)，解題思路和15題基本一致。
No.19.刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)
難度：中等
題目描述：
題解代碼（Python3.8）
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy=ListNode(0)
dummy.next=head
i=0
p=dummy
while p:
p=p.next
i+=1
p=dummy
j=0
while True:
if j==i-1-n:
p.next=p.next.next
return dummy.next
p=p.next
j+=1
或許有用的知識(shí)點(diǎn)：
當(dāng)處理鏈表且需要考慮空鏈表時(shí)，我們或許可以設(shè)置一個(gè)啞結(jié)點(diǎn)，即dummy.next = head?？炻羔?biāo)枷耄ㄒ姟畠?yōu)解代碼及分析’）。
解題思路：
這個(gè)題要求刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。為了避免空鏈表的特殊情況，我們要設(shè)置一個(gè)啞節(jié)點(diǎn)。因?yàn)殒湵硎菃蜗虻?，我們首先要知道鏈表的總長度i，再將第i-1-n個(gè)節(jié)點(diǎn)直向下下個(gè)節(jié)點(diǎn)即可，最后我們返回啞節(jié)點(diǎn)的下個(gè)節(jié)點(diǎn)即為原鏈表的頭節(jié)點(diǎn)。
優(yōu)解代碼及分析：
優(yōu)解代碼（Python3.8）
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
# 增加一個(gè)啞節(jié)點(diǎn)方便邊界判斷
dummy = ListNode(0)
dummy.next,a,b = head,dummy,dummy
# 第一個(gè)循環(huán)，b指針先往前走n步
while n>0 and b:
b,n = b.next,n-1
# 假設(shè)整個(gè)鏈表長l<n，那么第一次遍歷完后b=NULL，于是后面的判斷就不用繼續(xù)了，直接返回
if not b:
 return head
# 第二次，b指針走到鏈表最后，a指針也跟著走，當(dāng)b=NULL時(shí)遍歷結(jié)束，a指針就指向要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)位置
while b.next:
a,b = a.next,b.next
# 刪除節(jié)點(diǎn)并返回
a.next = a.next.next
return dummy.next
分析：
使用了快慢指針?biāo)枷?，只用了一次遍歷就找到了倒數(shù)第n個(gè)節(jié)點(diǎn)。如需快慢指針的具體內(nèi)容和其他用途可以查看本題‘或許有用的知識(shí)點(diǎn)’中的鏈接。
No.20.有效的括號(hào)
難度：簡(jiǎn)單
題目描述：
題解代碼（Python3.8）
class Solution:
def isValid(self, s: str) -> bool:
stack=['?']
dic={')':'(','}':'{',']':'['}
for char in s:
if char in dic:
top=stack.pop()
if top != dic[char]:
return False
else:
stack.append(char)
return stack==['?']
或許有用的知識(shí)點(diǎn)：
temp=list.pop()，是彈出list中最后一個(gè)元素，并儲(chǔ)存到temp中，list.pop()就是直接彈出最后一個(gè)元素。
解決括號(hào)配對(duì)這類二元就近配對(duì)的問題，可以運(yùn)用棧的思想。
解題思路：設(shè)‘（’類的為開括號(hào)，‘）’類的為閉括號(hào)，設(shè)置一個(gè)字典dic={‘閉括號(hào)（key）’：’開括號(hào)（value）’}。用for循環(huán)遍歷字符串中每一個(gè)字符，如果這個(gè)字符是開括號(hào)（不是dic的key），就把它寫入list中，如果這個(gè)字符是閉括號(hào)，就彈出list中最后一個(gè)字符，判斷與該字符對(duì)應(yīng)字符是否相等，不相等則False。為了防止開括號(hào)數(shù)量小造成閉括號(hào)匹配出錯(cuò)的情況，我們應(yīng)先給list賦一個(gè)初值，最后返回判斷l(xiāng)ist是否與初值相同的布爾值。
