中等難度-DFS

來(lái)源leetcode熱題HOT100中46,98,105,114,207,337,394

46.全排列

  • 題目描述
    • 給定一個(gè) 沒(méi)有重復(fù) 數(shù)字的序列，返回其所有可能的全排列。
  • 示例
輸入: [1,2,3]
輸出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
  • 題解：
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # 深度搜索主程序
        def dfs(nums,size,depth,path,used,res):
            if depth == size:
                res.append(path[:])
                return
            for i in range(size):
                if not used[I]:
                    used[i] = True
                    path.append(nums[I])
                    
                    dfs(nums,size,depth+1,path,used,res)
                    used[i] = False
                    path.pop()
        '''
        depth:表示當(dāng)前遞歸到第幾層
        為了區(qū)分不同階段，用兩個(gè)狀態(tài)變量記錄：
        (1)path:已經(jīng)選了哪些數(shù)，到葉節(jié)點(diǎn)時(shí)，這些數(shù)就構(gòu)成一個(gè)全排列
        (2)布爾數(shù)組used，初始化為false表示都沒(méi)有被選擇
        '''
        size = len(nums)
        if len(nums) == 0:
            return []
        
        used = [False for _ in range(size)]
        res = []
        dfs(nums,size,0,[],used,res)
        return res

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

  • 題目描述
    • 給定一個(gè)二叉樹，判斷其是否是一個(gè)有效的二叉搜索樹。
      假設(shè)一個(gè)二叉搜索樹具有如下特征：
      節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。
      節(jié)點(diǎn)的右子樹只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)。
      所有左子樹和右子樹自身必須也是二叉搜索樹。
  • 示例
示例 1:

輸入:
    2
   / \
  1   3
輸出: true
示例 2:

輸入:
    5
   / \
  1   4
     / \
    3   6
輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]。
     根節(jié)點(diǎn)的值為 5 ，但是其右子節(jié)點(diǎn)值為 4 。
  • 題解
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def dfs(node, min_val, max_val):
            if not node:  # 邊界條件，如果node為空肯定是二叉搜索樹
                return True
            # 如果當(dāng)前節(jié)點(diǎn)超出上下界范圍，肯定不是
            if not min_val < node.val < max_val:  
                return False
            # 走到下面這步說(shuō)明已經(jīng)滿足了如題所述的二叉搜索樹的前兩個(gè)條件
            # 那么只需要遞歸判斷當(dāng)前節(jié)點(diǎn)的左右子樹是否同時(shí)是二叉搜索樹即可
            return dfs(node.left, min_val, node.val) and dfs(node.right, node.val, max_val)
        # 對(duì)于根節(jié)點(diǎn)，它的上下限為無(wú)窮大和無(wú)窮小
        return dfs(root, float('-inf'), float('inf'))

105.從前序和中序遍歷序列構(gòu)造二叉樹

  • 題目描述
    • 根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹。
  • 示例
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：

    3
   / \
  9  20
    /  \
   15   7
  • 題解
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:  # 遞歸終止條件
            return
        root = TreeNode(preorder[0])  # 先序?yàn)椤案笥摇?，所以根?jù)preorder可以確定root
        idx = inorder.index(preorder[0])  # 中序?yàn)椤白蟾摇保鶕?jù)root可以劃分出左右子樹
        # 下面遞歸對(duì)root的左右子樹求解即可
        root.left = self.buildTree(preorder[1:1 + idx], inorder[:idx])
        root.right = self.buildTree(preorder[1 + idx:], inorder[idx + 1:])
        return root

114.二叉樹展開為鏈表

  • 題目描述：

    • 給定一個(gè)二叉樹，將它展開為一個(gè)單鏈表。

  • 示例：

例如，給定二叉樹

    1
   / \
  2   5
 / \   \
3   4   6
將其展開為：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
  • 題解：
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        while root:
            if root.left:   #左子樹存在的話才進(jìn)行操作
                sub_left = root.left
                while sub_left.right:   #左子樹的右子樹找到最深
                    sub_left = sub_left.right
                sub_left.right = root.right #將root的右子樹掛到左子樹的右子樹的最深
                root.right = root.left      #將root的左子樹掛到右子樹
                root.left = None            #將root左子樹清空
            root = root.right               #繼續(xù)下一個(gè)節(jié)點(diǎn)的操作

207.課程表

  • 題目描述：
    • 你這個(gè)學(xué)期必須選修 numCourse 門課程，記為 0 到 numCourse-1 。
      在選修某些課程之前需要一些先修課程。 例如，想要學(xué)習(xí)課程 0 ，你需要先完成課程 1 ，我們用一個(gè)匹配來(lái)表示他們：[0,1]
      給定課程總量以及它們的先決條件，請(qǐng)你判斷是否可能完成所有課程的學(xué)習(xí)？
  • 示例

示例 1:
輸入: 2, [[1,0]]
輸出: true
解釋: 總共有 2 門課程。學(xué)習(xí)課程 1 之前，你需要完成課程 0。所以這是可能的。
示例 2:
輸入: 2, [[1,0],[0,1]]
輸出: false
解釋: 總共有 2 門課程。學(xué)習(xí)課程 1 之前，你需要先完成?課程 0；并且學(xué)習(xí)課程 0 之前，你還應(yīng)先完成課程 1。這是不可能的

  • 題解：
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        '''
        有向無(wú)圈圖DAG，如果構(gòu)成環(huán)路是不成立的
        通過(guò)拓?fù)渑判蚺袛嗍欠袷荄AG：
            對(duì)DAG對(duì)頂點(diǎn)進(jìn)行排序，使得每一條有向邊(u,v),均符合y比v先出現(xiàn)
        DFS解法
        借助一個(gè)列表flags用于判斷每個(gè)節(jié)點(diǎn)的狀態(tài)：
            未被訪問(wèn)，i==0
            已被其他節(jié)點(diǎn)啟動(dòng)的DFS訪問(wèn)，i==-1
            已被當(dāng)前節(jié)點(diǎn)啟動(dòng)的DFS訪問(wèn)，i==1
        對(duì)numCourses個(gè)節(jié)點(diǎn)依次執(zhí)行DFS，判斷是否有環(huán)：
            當(dāng)flags[i]==-1,被其他節(jié)點(diǎn)訪問(wèn)過(guò)，返回True
            當(dāng)flags[i]==1,已在本輪搜索中訪問(wèn)過(guò)，即有環(huán)，返回False
            將當(dāng)前節(jié)點(diǎn)i對(duì)應(yīng)flags[i]置為1，表示本輪訪問(wèn)過(guò)
            遞歸訪問(wèn)當(dāng)前節(jié)點(diǎn)i的所有鄰接節(jié)點(diǎn)j，發(fā)現(xiàn)環(huán)返回False
            當(dāng)前節(jié)點(diǎn)的所有鄰接節(jié)點(diǎn)也被遍歷，則當(dāng)前節(jié)點(diǎn)置為-1，返回True
        如果整個(gè)圖DFS結(jié)束都沒(méi)發(fā)現(xiàn)環(huán)，返回True
        '''
        def dfs(i,adjacency,flags):
            #終止條件
            if flags[i] == -1:
                return True
            if flags[i] == 1:
                return False
            #當(dāng)前點(diǎn)置為1
            flags[i] = 1
            #對(duì)當(dāng)前節(jié)點(diǎn)對(duì)所有鄰接點(diǎn)進(jìn)行dfs
            for j in adjacency[I]:
                if not dfs(j,adjacency,flags):
                    return False
            #沒(méi)有環(huán)則當(dāng)前節(jié)點(diǎn)置為-1，下次不需要再進(jìn)行dfs了，返回True
            flags[i] = -1
            return True
        #
        adjacency = [[] for _ in range(numCourses)]
        flags = [0 for _ in range(numCourses)]
        for cur,pre in prerequisites:
            adjacency[pre].append(cur)
        #對(duì)所有節(jié)點(diǎn)進(jìn)行dfs
        for i in range(numCourses):
            if not dfs(i,adjacency,flags):
                return False
        return True

        '''
        BFS解法：
        統(tǒng)計(jì)課程安排圖中每個(gè)節(jié)點(diǎn)的入度，生成入度表indegrees
        借助一個(gè)隊(duì)列queue，將所有入度為0的節(jié)點(diǎn)入隊(duì)
        當(dāng)queue不為空，依次隊(duì)首節(jié)點(diǎn)出隊(duì)，在課程安排圖中刪除此節(jié)點(diǎn)pre
            并不是真正從鄰接表刪除，而是此節(jié)點(diǎn)對(duì)應(yīng)所有鄰接節(jié)點(diǎn)cur-1
            當(dāng)入度-1后鄰接節(jié)點(diǎn)cur的入度為0，說(shuō)明cur的前驅(qū)節(jié)點(diǎn)已經(jīng)被刪除，此時(shí)cur入隊(duì)
        在每次pre出隊(duì)時(shí)，執(zhí)行numCourses--
            若課程安排圖是DAG，則所有節(jié)點(diǎn)都出隊(duì)入隊(duì)過(guò)
            如圖中存在環(huán)，則一定有節(jié)點(diǎn)的入度始終不為0
            拓?fù)渑判虺鲫?duì)次數(shù)等于課程個(gè)數(shù)，返回numCourses==0可以判斷是否成功
        '''
        
        #入度表
        indegrees = [0 for _ in range(numCourses)]
        #課程的依賴
        adjacency = [[] for _ in range(numCourses)]
        queue = collections.deque()
        # 入度表記錄所有節(jié)點(diǎn)的入度，
        for cur,pre in prerequisites:
            indegrees[cur] += 1
            adjacency[pre].append(cur)
        #入度不為0的加入隊(duì)列
        for i in range(len(indegrees)):
            if not indegrees[I]:
                queue.append(i)
        #BFS
        while queue:
            #取出隊(duì)首數(shù)據(jù)
            pre = queue.popleft()
            numCourses -= 1
            #遍歷隊(duì)首的所有鄰接元素
            for cur in adjacency[pre]:
                indegrees[cur] -= 1
                #如果鄰接元素入度-1后還不為0，則將其加入隊(duì)列
                if not indegrees[cur]:
                    queue.append(cur)
        return numCourses == 0

337.打家劫舍三

  • 題目描述

    • 在上次打劫完一條街道之后和一圈房屋后，小偷又發(fā)現(xiàn)了一個(gè)新的可行竊的地區(qū)。這個(gè)地區(qū)只有一個(gè)入口，我們稱之為“根”。 除了“根”之外，每棟房子有且只有一個(gè)“父“房子與之相連。一番偵察之后，聰明的小偷意識(shí)到“這個(gè)地方的所有房屋的排列類似于一棵二叉樹”。 如果兩個(gè)直接相連的房子在同一天晚上被打劫，房屋將自動(dòng)報(bào)警。
      計(jì)算在不觸動(dòng)警報(bào)的情況下，小偷一晚能夠盜取的最高金額。

  • 示例


    image.png

  • 題解

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    '''
    每一個(gè)節(jié)點(diǎn)有偷與不偷兩種選擇：
    每一個(gè)節(jié)點(diǎn)如果偷的話值為：
        左側(cè)子節(jié)點(diǎn)不偷的值 + 右側(cè)子節(jié)點(diǎn)不偷的值 + 該節(jié)點(diǎn)的值
    每一個(gè)節(jié)點(diǎn)如果不偷的話值為：
        左側(cè)子節(jié)點(diǎn)的最大值 + 右側(cè)子節(jié)點(diǎn)的最大值
    '''
    def rob(self,root):
        # a為一個(gè)二維數(shù)組，為root的[偷值,不偷值]
        a = self.helper(root)
        # 返回兩個(gè)值的最大值
        return max(a[0],a[1])
    #參數(shù)為root節(jié)點(diǎn)，返回二維數(shù)組，root的[偷值,不偷值]
    def helper(self,root):
        if not root:
            return [0,0]
        left = self.helper(root.left)
        right = self.helper(root.right)
        # root的偷值
        robValue = left[1] + right[1] +root.val
        # root的不偷值
        skipValue = max(left[0],left[1]) + max(right[0],right[1])
        return [robValue,skipValue]

394.字符串解碼

  • 題目描述

    • 給定一個(gè)經(jīng)過(guò)編碼的字符串，返回它解碼后的字符串。
      編碼規(guī)則為: k[encoded_string]，表示其中方括號(hào)內(nèi)部的 encoded_string 正好重復(fù) k 次。注意 k 保證為正整數(shù)。
      你可以認(rèn)為輸入字符串總是有效的；輸入字符串中沒(méi)有額外的空格，且輸入的方括號(hào)總是符合格式要求的。
      此外，你可以認(rèn)為原始數(shù)據(jù)不包含數(shù)字，所有的數(shù)字只表示重復(fù)的次數(shù) k ，例如不會(huì)出現(xiàn)像 3a 或 2[4] 的輸入。

  • 示例


    image.png

  • 題解

class Solution:
    def decodeString(self, s: str) -> str:
        '''
        輔助棧法
        構(gòu)建輔助棧stack，遍歷字符串s中的每個(gè)字符c：
            當(dāng)c為數(shù)字時(shí)，將數(shù)字字符轉(zhuǎn)換為數(shù)字multi
            當(dāng)c為字母時(shí)，在res結(jié)尾添加c
            當(dāng)c為[時(shí)，將當(dāng)前multi和res入棧，并分別置空
                記錄此[前當(dāng)臨時(shí)結(jié)果res入棧，用于發(fā)現(xiàn)對(duì)應(yīng)]后的拼接操作
                記錄[前的multi入棧，用于發(fā)現(xiàn)對(duì)應(yīng)]后，獲取multi*[]字符串
            當(dāng)c為]時(shí)，stack出棧，拼接字符串res = last_res + cur_multi*res
                last_res是上個(gè)[到當(dāng)前[的字符串
                cur_multi是當(dāng)前[到]內(nèi)字符串的重復(fù)次數(shù)
        '''
        stack = []
        res = ''
        multi = 0
        for c in s:
            if c == '[':
                stack.append([multi,res])
                res,multi = '',0
            elif c == ']':
                cur_multi,last_res = stack.pop()
                res = last_res + cur_multi * res
            elif '0' <= c <= '9':
                #處理數(shù)字不是個(gè)位數(shù)的情況
                multi = multi*10 + int(c)
            else:
                res += c
        return res
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容