Python小白 Leetcode刷題歷程 No.96-No.100 不同的二叉搜索樹赞赖、交錯字符串冤灾、驗證二叉搜索樹、恢復(fù)二叉搜索樹韵吨、相同的樹
寫在前面：
作為一個計算機院的大學(xué)生，總覺得僅僅在學(xué)校粗略的學(xué)習(xí)計算機專業(yè)課是不夠的椿疗，尤其是假期大量的空檔期糠悼，作為一個小白，實習(xí)也莫得路子倔喂，又不想白白耗費時間。于是選擇了Leetcode這個平臺來刷題庫攻晒。編程我只學(xué)過基礎(chǔ)的C語言班挖，現(xiàn)在在自學(xué)Python，所以用Python3.8刷題庫。現(xiàn)在我Python掌握的還不是很熟練假丧，算法什么的也還沒學(xué)动羽，就先不考慮算法上的優(yōu)化了，單純以解題為目的运吓，復(fù)雜程度什么的以后有時間再優(yōu)化。計劃順序五個題寫一篇日志谋梭，希望其他初學(xué)編程的人起到一些幫助倦青，寫算是對自己學(xué)習(xí)歷程的一個見證了吧。
有一起刷LeetCode的可以關(guān)注我一下产镐，我會一直發(fā)LeetCode題庫Python3解法的花竞，也可以一起探討。
覺得有用的話可以點贊關(guān)注下哦逃糟，謝謝大家蓬豁！
········································································································································································
題解框架：
1.題目，難度
2.題干,題目描述
3.題解代碼（Python3（不是Python地粪，是Python3））
4.或許有用的知識點（不一定有）
5.解題思路
6.優(yōu)解代碼及分析（當我發(fā)現(xiàn)有比我寫的好很多的代碼和思路我就會寫在這里）
········································································································································································
No.96.不同的二叉搜索樹
難度：中等
題目描述：
題解代碼（Python3.8）
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
for i in range(2,n+1):
for j in range(i):
dp[i] += dp[j] * dp[i-j-1]
return dp[-1]
或許有用的知識點：
這道題要用到動態(tài)規(guī)劃的方法蟆技。
這道題所求的數(shù)在數(shù)學(xué)上又叫做卡特蘭數(shù)（Catalan number），具體介紹如下：
解題思路：
這道題是求解法總數(shù)的問題旺聚，我們可以使用動態(tài)規(guī)劃的方法眶蕉。套用動態(tài)規(guī)劃算法的模板，對于這道題碱璃，令dp[n]為第n位的解法總數(shù)，則動態(tài)規(guī)劃的三要素為：
狀態(tài)：假設(shè)n為根節(jié)點嵌器，當i為根節(jié)點時，其左子樹節(jié)點個數(shù)為[1,2,3,...,i-1]蚓让，右子樹節(jié)點個數(shù)為[i+1,i+2,...n]岳掐，所以當i為根節(jié)點時，其左子樹節(jié)點個數(shù)為i-1個串述，右子樹節(jié)點為n-i，即f(i) = G(i-1)G(n-i)衰腌。
狀態(tài)轉(zhuǎn)移方程：dp[i]+=dp[j]dp[i-j-1]
邊界條件：dp[0]=1,dp[1]=1觅赊。
No.97.交錯字符串
難度：困難
題目描述：
題解代碼（Python3.8）
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
l1 = len(s1)
l2 = len(s2)
l3 = len(s3)
if l1 + l2 != l3:
return False
dp = [[False]*(l2+1) for _ in range(l1+1)]
dp[0][0] = True #首位置
for j in range(1,l2+1): #第一行
dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
for i in range(1,l1+1): #第一列
dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
for i in range(1,l1+1):
for j in range(1,l2+1):
dp[i][j] =(dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])
return dp[-1][-1]
或許有用的知識點：
這道題要處理字符串，驗證合法性饶囚，可以使用動態(tài)規(guī)劃的方法鸠补，且有動態(tài)規(guī)劃問題中‘自底向上’思路和‘自頂向下’思路區(qū)別的分析（‘自頂向下’的思路可能要用到‘緩存+遞歸’的方法，此時會用到functools.lru_cache裝飾器紫岩，再本題’優(yōu)解代碼及分析中有詳細介紹‘）。
‘自底向上’的思路是比較容易想到的泉蝌，是先依次解決小問題，最終解決所求問題贪磺；在樹形結(jié)構(gòu)中诅愚，就是先解決底部的問題，再一層層解決向上的問題，最后解決頂部的所求問題苏研。
而‘自頂向下’的思路是比較不容易想到的腮郊，是先看解決最終問題依次需要解決哪些小問題，再解決所有的小問題轧飞；在樹形結(jié)構(gòu)中，就是先看解決頂部的問題需要解決哪些子問題大渤，再看解決這些子問題需要解決哪些子問題掸绞，直到解決最底部的問題。引用知乎大佬給出的生動形象的小例子：
某日小明上數(shù)學(xué)課衔掸，他的老師給了很多個不同的直角三角板讓小明用尺子去量三角板的三個邊烫幕，并將長度記錄下來。兩個小時過去敞映，小明完成任務(wù)较曼，把數(shù)據(jù)拿給老師。老師給他說振愿，還有一個任務(wù)就是觀察三條邊之間的數(shù)量關(guān)系捷犹。又是兩個小時，聰明的小明連蹦帶跳走進了辦公室冕末，說：“老師萍歉，我找到了，三條邊之中有兩條栓霜，它們的平方和約等于另外一條的平方翠桦『嵫眩”老師拍拍小明的頭胳蛮，“你今天學(xué)會了一個定理，勾股定理丛晌。它就是說直角三角形有兩邊平方和等于第三邊的平方和”。
另一個故事澎蛛，某日老師告訴小明“今天要教你一個定理抚垄，勾股定理。”小明說呆馁，“什么是勾股定理呢桐经？”“勾股定理是說，直角三角形中有兩條邊的平方和等于第三邊的平方浙滤∫跽酰”然后老師給了一大堆直角三角板給小明，讓他去驗證纺腊。兩個小時后畔咧，小明告訴老師定理是正確的.
兩個故事剛好是語法分析里面對應(yīng)的兩個方法：第一個故事說的是自底向上的分析方法，第二個故事說的是自頂而下的分析方法揖膜。
解題思路：
這道題是處理字符串誓沸，驗證合法性的問題，我們可以使用動態(tài)規(guī)劃的方法壹粟。套用動態(tài)規(guī)劃算法的模板拜隧，對于這道題，令dp[i][j]表示s1的前i個字符和s2的前j個字符是否能構(gòu)成s3的前i+j個字符,則動態(tài)規(guī)劃的三要素為：
狀態(tài)：
第i行第j列的狀態(tài)為：s1的前i-1個字符和s2的前j個字符能否構(gòu)成s3的前i+j?1位煮寡，且s1的第i位（s1[i?1]）是否等于s3的第i+j位（s3[i+j?1]）,或者s1的前i個字符和s2的前j?1個字符能否構(gòu)成s3的前i+j?1位虹蓄，且s2的第j位（s2[j?1]）是否等于s3的第i+j位（s3[i+j?1]）。
狀態(tài)轉(zhuǎn)移方程：dp[i][j] =(dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])
邊界條件：
dp[0][0] = True
for j in range(1,l2+1): dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
for i in range(1,l1+1): dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
優(yōu)解代碼及分析：
優(yōu)解代碼（Python3.8）
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
l1 = len(s1)
l2 = len(s2)
l3 = len(s3)
import functools
@functools.lru_cache(None)
def recursion(i,j,k):
if i == l1 and j == l2 and k == l3:
return True
if k < l3:
if i < l1 and s1[i] == s3[k] and recursion(i+1,j,k+1):
return True
if j < l2 and s2[j] == s3[k] and recursion(i,j+1,k+1):
return True
return False
return recursion(0,0,0)
分析：
這其實是緩存+遞歸的方式幸撕，原理和動態(tài)規(guī)劃一樣薇组。要用到functools.lru_cache裝飾器。
No.98.驗證二叉搜索樹
難度：中等
題目描述：
題解代碼（Python3.8）
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
res = []
def recursion(root):
if not root:
return
recursion(root.left)
res.append(root.val)
recursion(root.right)
recursion(root)
return (res == sorted(res)) and (len(set(res)) == len(res))
或許有用的知識點：
這道題使用了遞歸的思想坐儿。
解題思路：
因為二叉搜索樹中序遍歷是遞增的,所以我們可以中序遍歷判斷前一數(shù)是否小于后一個數(shù)律胀。運用遞歸的方法，設(shè)置一個遞歸函數(shù)貌矿，將整個樹從左到右輸出炭菌，在判斷是否遞增。
No.99.恢復(fù)二叉搜索樹
難度：困難
題目描述：
題解代碼（Python3.8）
class Solution:
def recoverTree(self, root: TreeNode) -> None:
self.firstNode = None
self.secondNode = None
self.preNode = TreeNode(float('-inf'))
def recursion(root):
if not root:
return
recursion(root.left)
if (self.firstNode == None) and (self.preNode.val >= root.val):
self.firstNode = self.preNode
if self.firstNode and (self.preNode.val >= root.val):
self.secondNode =root
self.preNode = root
recursion(root.right)
recursion(root)
self.firstNode.val,self.secondNode.val = self.secondNode.val,self.firstNode.val
或許有用的知識點：
這道題用了遞歸的思想逛漫。
這道題firstNode,secondNode,preNode三個變量在多個函數(shù)中被引用黑低，可以在變量前加’self.’。
float("inf"), float("-inf")分別表示正負無窮酌毡。
解題思路：
這道題難點,是找到那兩個交換了的節(jié)點,把它交換過來就行了克握。這里我們二叉樹搜索樹的中序遍歷(中序遍歷遍歷元素是遞增的)，如下圖所示, 中序遍歷順序是 4,2,3,1,我們只要找到節(jié)點4和節(jié)點1交換順序即可枷踏。這里我們有個規(guī)律發(fā)現(xiàn)這兩個節(jié)點：第一個節(jié)點,是第一個按照中序遍歷時候前一個節(jié)點大于后一個節(jié)點,我們選取前一個節(jié)點,這里指節(jié)點4;第二個節(jié)點,是在第一個節(jié)點找到之后, 后面出現(xiàn)前一個節(jié)點大于后一個節(jié)點,我們選擇后一個節(jié)點,這里指節(jié)點1菩暗。
No.100.相同的樹
難度：簡單
題目描述：
題解代碼（Python3.8）
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if (not p) and (not q):
return True
if (p and q) and (p.val == q.val):
return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
return False
或許有用的知識點：
這道題要用到遞歸的思想。
解題思路：
這道題運用遞歸的方法旭蠕，設(shè)置一個遞歸函數(shù)停团，當p和q都空時return True旷坦；當p和q都非空時，如果p和q的值相等佑稠，return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)秒梅，判斷p和q的左右子支的值是否相等。
