Python小白 Leetcode刷题历程 No.91-No.95 解码方法、反转链表Ⅱ、复原IP地址、二叉树的中序遍历、不同的二叉搜索树Ⅱ
写在前面：
作为一个计算机院的大学生，总觉得仅仅在学校粗略的学习计算机专业课是不够的，尤其是假期大量的空档期，作为一个小白，实习也莫得路子，又不想白白耗费时间。于是选择了Leetcode这个平台来刷题库。编程我只学过基础的C语言，现在在自学Python，所以用Python3.8刷题库。现在我Python掌握的还不是很熟练，算法什么的也还没学，就先不考虑算法上的优化了，单纯以解题为目的，复杂程度什么的以后有时间再优化。计划顺序五个题写一篇日志，希望其他初学编程的人起到一些帮助，写算是对自己学习历程的一个见证了吧。
有一起刷LeetCode的可以关注我一下，我会一直发LeetCode题库Python3解法的，也可以一起探讨。
觉得有用的话可以点赞关注下哦，谢谢大家！
········································································································································································
题解框架：
1.题目，难度
2.题干,题目描述
3.题解代码（Python3（不是Python，是Python3））
4.或许有用的知识点（不一定有）
5.解题思路
6.优解代码及分析（当我发现有比我写的好很多的代码和思路我就会写在这里）
········································································································································································
No.91.解码方法
难度：中等
题目描述：
题解代码（Python3.8）
class Solution:
def numDecodings(self, s: str) -> int:
l = len(s)
dp = [0]*l
if s[0] == '0':
return 0
else:
dp[0] = 1
if l == 1:
return dp[-1]
if s[1] != '0':
dp[1] += 1
if 10 <= int(s[:2]) <=26:
dp[1] += 1
for i in range(2,l):
if s[i-1:i+1] == '00':
return 0
if s[i] != '0':
dp[i] += dp[i-1]
if 10 <= int(s[i-1:i+1]) <= 26:
dp[i] += dp[i-2]
return dp[-1]
或许有用的知识点：
这道题要用到动态规划的方法。
解题思路：
这道题是求解法总数的问题，我们可以使用动态规划的方法。套用动态规划算法的模板，对于这道题，令dp[i]为字符串到第i位的解码方法总数，则动态规划的三要素为：
状态：
如果连续出现两个‘0’，则无法解码，return 0；如果该位为不是‘0’，该位的解码数和上一位相同；如果该位和上一位属于[1,26]，上一位之前的数字独立合法，即该位的解码数再增加上上位的解码数。
状态转移方程：
if s[i-1:i+1] == '00': return 0
if s[i] != '0': dp[i] += dp[i-1]
if 10 <= int(s[i-1:i+1]) <= 26: dp[i] += dp[i-2]
边界条件：
if s[0] == '0': return 0
else: dp[0] = 1
if l == 1: return dp[-1]
if s[1] != '0': dp[1] += 1
if 10 <= int(s[:2]) <=26: dp[1] += 1
No.92.反转链表Ⅱ
难度：中等
题目描述：
题解代码（Python3.8）
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
dummy = ListNode(-1)
dummy.next = head
pre = dummy
for _ in range(m-1):
pre = pre.next
start = pre.next
tail = start.next
for _ in range(n-m):
start.next = tail.next
tail.next = pre.next
pre.next = tail
tail = start.next
return dummy.next
或许有用的知识点：
这道题要用到双指针思想的变式，多指针思想，利用三个指针实现链表部分的翻转。
解题思路：
用三个指针,进行插入操作。例如:1->2->3->4->5->NULL, m = 2, n = 4，将节点3插入节点1和节点2之间，变成: 1->3->2->4->5->NULL；再将节点4插入节点1和节点3之间，变成:1->4->3->2->5->NULL，实现翻转的效果。
No.93.复原IP地址
难度：中等
题目描述：
题解代码（Python3.8）
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
l = len(s)
def backtrack(i,tmp,flag):
if i == l and flag == 0:
res.append(tmp[:-1])
return
if flag < 0:
return
for j in range(i,i+3):
if j < l:
if i == j and s[j] == '0':
backtrack(j+1,tmp+s[j]+'.',flag-1)
break
if 0 < int(s[i:j+1]) <= 255:
backtrack(j+1,tmp+s[i:j+1]+'.',flag-1)
backtrack(0,'',4)
return res
或许有用的知识点：
这道题要用到回溯算法。
解题思路：
这道题要求返回所有可能的IP地址形式，所以要用到回溯算法。套用回溯算法的模板，则回溯函数的三个组成部分分别为：
1.回溯出口：因为要将IP地址分成四个部分，令初始Flag值为4，确定一个部分Flag减一，当i==l and Flag==0时，res.append(tmp[:-1])并返回（当Flag<0直接返回）。
2.回溯主体：在j属于[i,i+3)且j<l时，如果i == j and s[j] == '0'，说明确定了一个部分，进行下一轮回溯，之后break跳出；如果0 < int(s[i:j+1]) <= 255，说明确定了一个部分，进行下一轮回溯。
3.状态返回：因为回溯的过程并没有改变全局变量，所以不需要状态返回。
No.94.二叉树的中序遍历
难度：中等
题目描述：
题解代码（Python3.8）
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def Traversal(root):
if not root:
return
Traversal(root.left)
res.append(root.val)
Traversal(root.right)
Traversal(root)
return res
或许有用的知识点：
这道二叉树的题我们可以使用递归的方法。
这道二叉树的题我们还可以用迭代+栈的方法。
中序遍历可以理解为将整个数从左到右输出，具体定义如下：
解题思路：
上面的题解是运用了递归的方法，设置一个递归函数，将整个树从左到右输出。
优解代码及分析：
优解代码（Python3.8）
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
p = root
while p or stack:
while p:
stack.append(p)
p = p.left
p = stack.pop()
res.append(p.val)
p = p.right
return res
分析：
这道题我们运用了迭代+栈的方法，创建一个栈，先将左子树压入栈中，通过输出栈顶元素，将整个树从左到右输出。
No.95.不同的二叉搜索树Ⅱ
难度：中等
题目描述：
题解代码（Python3.8）
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
if n == 0:
return []
import functools
@functools.lru_cache
def recursion(start,end):
res = []
if start >end:
res.append(None)
for val in range(start,end+1):
for left in recursion(start,val-1):
for right in recursion(val+1,end):
root = TreeNode(val)
root.left = left
root.right = right
res.append(root)
return res
return recursion(1,n)
或许有用的知识点：
这其实是缓存+递归的方式，原理和动态规划一样。要用到functools.lru_cache装饰器。
解题思路：
这道题是求对于1-n为节点的二叉树的所有结构，我们用缓存+递归的方式，动态规划的原理，使用functools.lru_cache装饰器，进行高效的动态规划（自顶向下）。先特判，若start>end， res.append(None) ；之后遍历1-n，找的一个节点值val，再通过递归函数找到这个节点的left和right，将这种结构输入进结果res即可。
