Python小白 Leetcode刷题历程 No.16-No.20 最接近的三数之和、Phone Number的字母组合、四数之和、删除链表的倒数第N个节点、有效的括号
写在前面：
作为一个计算机院的大学生，总觉得仅仅在学校粗略的学习计算机专业课是不够的，尤其是假期大量的空档期，作为一个小白，实习也莫得路子，又不想白白耗费时间。于是选择了Leetcode这个平台来刷题库。编程我只学过基础的C语言，现在在自学Python，所以用Python3.8刷题库。现在我Python掌握的还不是很熟练，算法什么的也还没学，就先不考虑算法上的优化了，单纯以解题为目的，复杂程度什么的以后有时间再优化。计划顺序五个题写一篇日志，希望其他初学编程的人起到一些帮助，写算是对自己学习历程的一个见证了吧。
有一起刷LeetCode的可以关注我一下，我会一直发LeetCode题库Python3解法的，也可以一起探讨。
觉得有用的话可以点赞关注下哦，谢谢大家！
········································································································································································
题解框架：
1.题目，难度
2.题干,题目描述
3.题解代码（Python3（不是Python，是Python3））
4.或许有用的知识点（不一定有）
5.解题思路
6.优解代码及分析（当我发现有比我写的好很多的代码和思路我就会写在这里）
········································································································································································
No.16.最接近的三数之和
难度:中等
题目描述：
题解代码（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
或许有用的知识点：
abs(x)=x的绝对值。
解题思路：
第十五题‘No.15.三数之和’思路类似，从一个数组中确定三个数，可以先for循环确定一个数，再用双指针法确定后两个数，然后判断，根据判断结果移动指针直到不满足L<R。
No.17.电话号码的字母组合
难度：中等
题目描述：
题解代码（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
或许有用的知识点：
回溯算法，在树形结构中找全部的解，通常使用回溯算法。
解题思路：
对与“23”我们不难推断出它的解为下图：
这显然是在树形结构求树叶的全部解，在树形结构中找全部的解，通常使用回溯算法。
先写出这个题的字典，phone={‘数字（key）’：‘对应字母（value）’}，然后定义回溯函数运算即可，当剩余数字长度为0，结束循环，否则，for遍历这个数字的所有字母值，在每个循环中再次进行回溯函数。
No.18.四数之和
难度：中等
题目描述：
题解代码（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: #最小数>target/4，跳出循环
break
if i>0 and nums[i]==nums[i-1]: #最小数与上一轮循环相同，防止重复解，跳过
continue
for j in range(l)[::-1]:
if nums[j]<(target/4)-1: #最大数<target/4，跳出循环
break
if j<l-1 and nums[j]==nums[j+1]: #最大数与上一轮循环相同，防止重复解，跳过
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]: #左指针向右跳过重复值，防止重复解
L +=1
while L<R and nums[R]==nums[R-1]: #右指针向左跳过重复值，防止重复解
R -=1
L +=1
R -=1
elif nums[i]+nums[L]+nums[R]+nums[j] > target: #四数和>0，右指针大了，左移
R -=1
else: #四数和<0，左指针小了，右移
L +=1
return res
解题思路：
这题跟例题第十五题‘No.15.三数之和’基本一致，只不过多了个数，我们可以确定一个最大数和一个最小数，中间两数用双指针。这道题我代码中的标注很详细，解题思路和15题基本一致。
No.19.删除链表的倒数第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
或许有用的知识点：
当处理链表且需要考虑空链表时，我们或许可以设置一个哑结点，即dummy.next = head。快慢指针思想（见‘优解代码及分析’）。
解题思路：
这个题要求删除链表的倒数第 n 个节点，并且返回链表的头结点。为了避免空链表的特殊情况，我们要设置一个哑节点。因为链表是单向的，我们首先要知道链表的总长度i，再将第i-1-n个节点直向下下个节点即可，最后我们返回哑节点的下个节点即为原链表的头节点。
优解代码及分析：
优解代码（Python3.8）
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
# 增加一个哑节点方便边界判断
dummy = ListNode(0)
dummy.next,a,b = head,dummy,dummy
# 第一个循环，b指针先往前走n步
while n>0 and b:
b,n = b.next,n-1
# 假设整个链表长l<n，那么第一次遍历完后b=NULL，于是后面的判断就不用继续了，直接返回
if not b:
 return head
# 第二次，b指针走到链表最后，a指针也跟着走，当b=NULL时遍历结束，a指针就指向要删除的节点的前一个位置
while b.next:
a,b = a.next,b.next
# 删除节点并返回
a.next = a.next.next
return dummy.next
分析：
使用了快慢指针思想，只用了一次遍历就找到了倒数第n个节点。如需快慢指针的具体内容和其他用途可以查看本题‘或许有用的知识点’中的链接。
No.20.有效的括号
难度：简单
题目描述：
题解代码（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==['?']
或许有用的知识点：
temp=list.pop()，是弹出list中最后一个元素，并储存到temp中，list.pop()就是直接弹出最后一个元素。
解决括号配对这类二元就近配对的问题，可以运用栈的思想。
解题思路：设‘（’类的为开括号，‘）’类的为闭括号，设置一个字典dic={‘闭括号（key）’：’开括号（value）’}。用for循环遍历字符串中每一个字符，如果这个字符是开括号（不是dic的key），就把它写入list中，如果这个字符是闭括号，就弹出list中最后一个字符，判断与该字符对应字符是否相等，不相等则False。为了防止开括号数量小造成闭括号匹配出错的情况，我们应先给list赋一个初值，最后返回判断list是否与初值相同的布尔值。
