Python小白 Leetcode刷題歷程 No.96-No.100 不同的二叉搜索樹(shù)、交錯(cuò)字符串、驗(yàn)證二叉搜索樹(shù)、恢復(fù)二叉搜索樹(shù)、相同的樹(shù)

寫(xiě)在前面：

作為一個(gè)計(jì)算機(jī)院的大學(xué)生，總覺(jué)得僅僅在學(xué)校粗略的學(xué)習(xí)計(jì)算機(jī)專(zhuān)業(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é)得有用的話(huà)可以點(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.96.不同的二叉搜索樹(shù)

難度：中等
題目描述：

在這里插入圖片描述

題解代碼（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]

或許有用的知識(shí)點(diǎn)：
這道題要用到動(dòng)態(tài)規(guī)劃的方法。
這道題所求的數(shù)在數(shù)學(xué)上又叫做卡特蘭數(shù)（Catalan number），具體介紹如下：

在這里插入圖片描述

在這里插入圖片描述

解題思路：
這道題是求解法總數(shù)的問(wèn)題，我們可以使用動(dòng)態(tài)規(guī)劃的方法。套用動(dòng)態(tài)規(guī)劃算法的模板，對(duì)于這道題，令dp[n]為第n位的解法總數(shù)，則動(dòng)態(tài)規(guī)劃的三要素為：
狀態(tài)：假設(shè)n為根節(jié)點(diǎn)，當(dāng)i為根節(jié)點(diǎn)時(shí)，其左子樹(shù)節(jié)點(diǎn)個(gè)數(shù)為[1,2,3,...,i-1]，右子樹(shù)節(jié)點(diǎn)個(gè)數(shù)為[i+1,i+2,...n]，所以當(dāng)i為根節(jié)點(diǎn)時(shí)，其左子樹(shù)節(jié)點(diǎn)個(gè)數(shù)為i-1個(gè)，右子樹(shù)節(jié)點(diǎn)為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.交錯(cuò)字符串

難度：困難
題目描述：

在這里插入圖片描述

題解代碼（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]

或許有用的知識(shí)點(diǎn)：
這道題要處理字符串，驗(yàn)證合法性，可以使用動(dòng)態(tài)規(guī)劃的方法，且有動(dòng)態(tài)規(guī)劃問(wèn)題中‘自底向上’思路和‘自頂向下’思路區(qū)別的分析（‘自頂向下’的思路可能要用到‘緩存+遞歸’的方法，此時(shí)會(huì)用到functools.lru_cache裝飾器，再本題’優(yōu)解代碼及分析中有詳細(xì)介紹‘）。
‘自底向上’的思路是比較容易想到的，是先依次解決小問(wèn)題，最終解決所求問(wèn)題；在樹(shù)形結(jié)構(gòu)中，就是先解決底部的問(wèn)題，再一層層解決向上的問(wèn)題，最后解決頂部的所求問(wèn)題。
而‘自頂向下’的思路是比較不容易想到的，是先看解決最終問(wèn)題依次需要解決哪些小問(wèn)題，再解決所有的小問(wèn)題；在樹(shù)形結(jié)構(gòu)中，就是先看解決頂部的問(wèn)題需要解決哪些子問(wèn)題，再看解決這些子問(wèn)題需要解決哪些子問(wèn)題，直到解決最底部的問(wèn)題。引用知乎大佬給出的生動(dòng)形象的小例子：
某日小明上數(shù)學(xué)課，他的老師給了很多個(gè)不同的直角三角板讓小明用尺子去量三角板的三個(gè)邊，并將長(zhǎng)度記錄下來(lái)。兩個(gè)小時(shí)過(guò)去，小明完成任務(wù)，把數(shù)據(jù)拿給老師。老師給他說(shuō)，還有一個(gè)任務(wù)就是觀察三條邊之間的數(shù)量關(guān)系。又是兩個(gè)小時(shí)，聰明的小明連蹦帶跳走進(jìn)了辦公室，說(shuō)：“老師，我找到了，三條邊之中有兩條，它們的平方和約等于另外一條的平方。”老師拍拍小明的頭，“你今天學(xué)會(huì)了一個(gè)定理，勾股定理。它就是說(shuō)直角三角形有兩邊平方和等于第三邊的平方和”。
另一個(gè)故事，某日老師告訴小明“今天要教你一個(gè)定理，勾股定理。”小明說(shuō)，“什么是勾股定理呢？”“勾股定理是說(shuō)，直角三角形中有兩條邊的平方和等于第三邊的平方?！比缓罄蠋熃o了一大堆直角三角板給小明，讓他去驗(yàn)證。兩個(gè)小時(shí)后，小明告訴老師定理是正確的.
兩個(gè)故事剛好是語(yǔ)法分析里面對(duì)應(yīng)的兩個(gè)方法：第一個(gè)故事說(shuō)的是自底向上的分析方法，第二個(gè)故事說(shuō)的是自頂而下的分析方法。

解題思路：
這道題是處理字符串，驗(yàn)證合法性的問(wèn)題，我們可以使用動(dòng)態(tài)規(guī)劃的方法。套用動(dòng)態(tài)規(guī)劃算法的模板，對(duì)于這道題，令dp[i][j]表示s1的前i個(gè)字符和s2的前j個(gè)字符是否能構(gòu)成s3的前i+j個(gè)字符,則動(dòng)態(tài)規(guī)劃的三要素為：
狀態(tài)：
第i行第j列的狀態(tài)為：s1的前i-1個(gè)字符和s2的前j個(gè)字符能否構(gòu)成s3的前i+j?1位，且s1的第i位（s1[i?1]）是否等于s3的第i+j位（s3[i+j?1]）,或者s1的前i個(gè)字符和s2的前j?1個(gè)字符能否構(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)

分析：
這其實(shí)是緩存+遞歸的方式，原理和動(dòng)態(tài)規(guī)劃一樣。要用到functools.lru_cache裝飾器。

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

No.98.驗(yàn)證二叉搜索樹(shù)

難度：中等
題目描述：

在這里插入圖片描述

題解代碼（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í)點(diǎn)：
這道題使用了遞歸的思想。

解題思路：
因?yàn)槎嫠阉鳂?shù)中序遍歷是遞增的,所以我們可以中序遍歷判斷前一數(shù)是否小于后一個(gè)數(shù)。運(yùn)用遞歸的方法，設(shè)置一個(gè)遞歸函數(shù)，將整個(gè)樹(shù)從左到右輸出，在判斷是否遞增。

No.99.恢復(fù)二叉搜索樹(shù)

難度：困難
題目描述：

在這里插入圖片描述

在這里插入圖片描述

題解代碼（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

或許有用的知識(shí)點(diǎn)：
這道題用了遞歸的思想。
這道題firstNode,secondNode,preNode三個(gè)變量在多個(gè)函數(shù)中被引用，可以在變量前加’self.’。
float("inf"), float("-inf")分別表示正負(fù)無(wú)窮。

解題思路：
這道題難點(diǎn),是找到那兩個(gè)交換了的節(jié)點(diǎn),把它交換過(guò)來(lái)就行了。這里我們二叉樹(shù)搜索樹(shù)的中序遍歷(中序遍歷遍歷元素是遞增的)，如下圖所示, 中序遍歷順序是 4,2,3,1,我們只要找到節(jié)點(diǎn)4和節(jié)點(diǎn)1交換順序即可。這里我們有個(gè)規(guī)律發(fā)現(xiàn)這兩個(gè)節(jié)點(diǎn)：第一個(gè)節(jié)點(diǎn),是第一個(gè)按照中序遍歷時(shí)候前一個(gè)節(jié)點(diǎn)大于后一個(gè)節(jié)點(diǎn),我們選取前一個(gè)節(jié)點(diǎn),這里指節(jié)點(diǎn)4;第二個(gè)節(jié)點(diǎn),是在第一個(gè)節(jié)點(diǎn)找到之后, 后面出現(xiàn)前一個(gè)節(jié)點(diǎn)大于后一個(gè)節(jié)點(diǎn),我們選擇后一個(gè)節(jié)點(diǎn),這里指節(jié)點(diǎn)1。

No.100.相同的樹(shù)

難度：簡(jiǎn)單
題目描述：

在這里插入圖片描述

題解代碼（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í)點(diǎn)：
這道題要用到遞歸的思想。

解題思路：
這道題運(yùn)用遞歸的方法，設(shè)置一個(gè)遞歸函數(shù)，當(dāng)p和q都空時(shí)return True；當(dāng)p和q都非空時(shí)，如果p和q的值相等，return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)，判斷p和q的左右子支的值是否相等。