iT邦幫忙

2024 iThome 鐵人賽

DAY 3
0
佛心分享-刷題不只是刷題

[30天LeetCode挑戰] 每天一點演算法,讓技巧融會貫通系列 第 3

[Day03] 關於DFS/BFS的4道題目筆記(257,994,199,752)

  • 分享至 

  • xImage
  •  

257. Binary Tree Paths

給定一棵 Binary Tree,要求找出所有從根節點到葉子節點的路徑,並以字符串形式返回,每一條路徑以「->」符號分隔節點。
用遞迴做的話一定會在這個函數下額外包一個 dfs 方法做,因為需要有變數儲存「->」這個文字。

class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: TreeNode
        :rtype: List[str]
        """
        out_str = ""
        all_out_str = []
        def dfs(out_str, all_out_str, root):
            if not root:
                return

            out_str += str(root.val)

            if not root.left and not root.right:
                all_out_str.append(out_str)
                return

            out_str += "->"
            dfs(out_str, all_out_str, root.left)
            dfs(out_str, all_out_str, root.right)
        dfs(out_str, all_out_str, root)

        return all_out_str

步驟如下:

  1. 遞迴遍歷:從根節點開始,沿著樹的每一條分支深入,直到達到葉子節點。
  2. 構造路徑:每當經過一個節點,將該節點的值加到當前路徑中。
  3. 判斷葉子節點:當一個節點的左右子節點均為空時,代表這是一個葉子節點,將完整路徑存入結果。
  4. 回溯:遍歷結束後回溯,繼續遍歷其他路徑。

994. Rotting Oranges

這題蠻有意思的,會有一個m x n的網格,其中每個單元格可以具有三個值之一:
0代表沒有橘子;1代表新鮮的橘子;2代表一個腐敗的橘子,
每經過一分鐘,任何與腐爛橘子相鄰的橘子會腐敗,要計算所有橘子腐敗時間要多久,如果最終無發讓所有橘子腐爛的話返回-1

from collections import deque
class Solution(object):
    def orangesRotting(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        queue = deque()
        fresh_oranges = 0
        rows, cols = len(grid), len(grid[0])  # 使用不同的變數保存行數和列數

        # Step 1: 初始化,把腐爛橘子的座標加入隊列,並統計新鮮橘子的數量
        for y in range(rows):
            for x in range(cols):
                if grid[y][x] == 2:
                    queue.append((x, y))  # 將座標作為元組加入隊列
                elif grid[y][x] == 1:
                    fresh_oranges += 1

        # 如果沒有新鮮橘子,直接返回 0
        if fresh_oranges == 0:
            return 0

        # Step 2: BFS 開始腐蝕橘子
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # 上下左右四個方向
        step = 0

        while queue:
            step += 1
            for _ in range(len(queue)):
                x, y = queue.popleft()
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    # 使用 cols 和 rows 來檢查範圍,而不是 x 和 y
                    if 0 <= nx < cols and 0 <= ny < rows and grid[ny][nx] == 1:
                        grid[ny][nx] = 2  # 新鮮橘子變腐爛
                        fresh_oranges -= 1
                        queue.append((nx, ny))  # 將新腐爛的橘子座標加入隊列

        # 如果還有新鮮橘子,無法完全腐爛,返回 -1
        return step - 1 if fresh_oranges == 0 else -1

這題想超久,主要是對queue還不太熟悉,再多寫幾題關於bfs的題目!

199. Binary Tree Right Side View

給定一棵二叉樹,想像自己站在二叉樹的右側,返回從右側可以看到的節點值的列表,就是對於每一層,從右邊可以看到的節點應該被加入結果最後返回。
使用bfs解題:

from collections import deque
def rightSideView_bfs(self, root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_length = len(queue)
        # 遍歷當前層的所有節點
        for i in range(level_length):
            node = queue.popleft()
            # 如果是該層的最後一個節點,將它加入結果
            if i == level_length - 1:
                result.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return result

使用dfs解題:

    def rightSideView_dfs(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result = []
        def dfs(node, level):
            if not node:
                return
            if level == len(result):
                result.append(node.val)
            dfs(node.right, level + 1)
            dfs(node.left, level + 1)
        dfs(root, 0)
        return result

752. Open the Lock

題目:有一個帶有四個轉盤的鎖,每個轉盤有 10 個數字,從 '0' 到 '9',轉動每一個轉盤使其向前或向後一位數,每次只能轉動一個轉盤。

鎖的初始組合是 "0000",給定一個目標組合 target,用最少的步驟將鎖的組合從 "0000" 轉到目標組合,但有一些「死亡組合」deadends,途中不能經過這些組合。
最終要返回將 "0000" 轉到 target 的最小步數,如果無法達到目標,則返回 -1

這題我完全沒有頭緒...只能先抄作業了

筆記

思路:
這是一個典型的"最短路徑問題",並且可以將每一個鎖的組合視作一個狀態,由於需要找出最少步數,因此我們可以使用"廣度優先搜索(BFS)",逐層展開最早找到的解即是最短的解。

步驟:
初始化:將初始組合 "0000" 作為起點加入隊列,同時我們使用一個集合來記錄死亡組合(deadends),以便在搜索過程中避開它們。
廣度優先搜索:
每次從隊列中取出當前狀態,將它與 target 進行比較。如果達到目標,則返回當前步數。
對當前鎖的每一位數,嘗試向上或向下轉動,並生成一個新的組合。如果這個組合不在 deadends 中,且還沒被訪問過,將它加入隊列。
結束條件:如果在 BFS 過程中找到 target,則返回當前步數。如果隊列變空,則返回-1,表示無法達到 target

from collections import deque

class Solution(object):
    def openLock(self, deadends, target):
        """
        :type deadends: List[str]
        :type target: str
        :rtype: int
        """
        # 將deadends轉為集合,方便快速查找
        dead_set = set(deadends)
        # 如果初始狀態就在deadends中,直接返回-1
        if "0000" in dead_set:
            return -1

        # 初始化BFS的隊列和已訪問集合
        queue = deque([("0000", 0)])  # 初始狀態是"0000",步數為0
        visited = set("0000")  # 記錄已訪問過的組合,避免重複訪問

        while queue:
            current, steps = queue.popleft()

            # 如果當前組合等於目標組合,返回步數
            if current == target:
                return steps

            # 嘗試對鎖的四個轉盤進行操作
            for i in range(4):
                # 對第 i 個轉盤,向上轉和向下轉
                for direction in [-1, 1]:
                    # 取出第i位的數字,將其轉為新的數字
                    new_digit = (int(current[i]) + direction) % 10
                    # 生成新的組合
                    new_combination = current[:i] + str(new_digit) + current[i + 1:]

                    # 如果新組合不在deadends且沒被訪問過,加入隊列
                    if new_combination not in dead_set and new_combination not in visited:
                        queue.append((new_combination, steps + 1))
                        visited.add(new_combination)

        # 如果無法達到目標,返回-1
        return -1

上一篇
[Day02] 關於DFS/BFS的3道題目筆記(112,733,200)
下一篇
[Day04] Array & List + Stack & Queue 筆記 LeetCode第232題題目筆記
系列文
[30天LeetCode挑戰] 每天一點演算法,讓技巧融會貫通30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言