合併所有重疊的區間

 

問題描述

給定一組任意順序的時間區間，目標是合併所有重疊的區間，並輸出只包含互不重疊區間的結果。

解決方案

1. 排序區間：首先根據每個區間的起始時間進行排序。這一步可以幫助我們輕鬆識別重疊的區間。

2. 初始化指標：使用 res_idx 來追蹤已合併的區間的最後索引，初始值設為 0。

3. 追踪區間：

   • 遍歷從第二個區間開始的所有區間。
   • 檢查當前區間是否與最後一個合併的區間重疊。
     • 如果重疊，則合併它們，更新結束時間。
     • 如果不重疊，則將當前區間添加到合併列表中，並增加 res_idx。

4. 返回合併後的區間數量：函數返回合併後的區間數量。

實現代碼

以下是 Python 的具體實現：

def merge_overlap(arr):
    if not arr:  # 檢查輸入是否為空
        return 0

    # 步驟 1：根據起始時間對區間進行排序
    arr.sort(key=lambda x: x[0])

    res_idx = 0  # 已合併區間的最後索引

    # 步驟 2：追踪區間
    for i in range(1, len(arr)):
        # 檢查當前區間是否與已合併區間重疊
        if arr[res_idx][1] >= arr[i][0]:
            # 合併重疊的區間
            arr[res_idx][1] = max(arr[res_idx][1], arr[i][1])
        else:
            # 如果不重疊，將當前區間加入合併列表
            res_idx += 1
            arr[res_idx] = arr[i]

    # 返回合併後的區間數量
    return res_idx + 1

# 驅動程式碼
if __name__ == "__main__":
    arr = [[6, 8], [1, 9], [2, 4], [4, 7]]

    # 獲取合併後的區間數量
    new_size = merge_overlap(arr)

    # 打印合併後的區間
    print("合併後的區間為:", end=" ")
    for i in range(new_size):
        print(f"[{arr[i][0]}, {arr[i][1]}]", end=" ")
    print()

測試輸出

對於輸入 arr = [[6, 8], [1, 9], [2, 4], [4, 7]]，執行上述代碼的輸出將是：

合併後的區間為: [1, 9]

總結

• 時間複雜度：排序過程的時間複雜度為 (O(n \log n))，合併過程的時間複雜度為 (O(n))，因此整體時間複雜度為 (O(n \log n))。
• 空間複雜度：使用的是原地合併，因此空間複雜度為 (O(1))。

資料來源：https://www.geeksforgeeks.org/merging-intervals/

將所有重疊的區間合併為一個，並輸出只包含互不重疊區間的結果

 

問題

給定一組任意順序的時間區間，我們的任務是將所有重疊的區間合併為一個，並輸出只包含互不重疊區間的結果。

解決步驟

1. 排序區間：首先，根據開始時間對區間進行排序，這樣可以更容易地識別重疊的區間。

2. 初始化合併列表：創建一個列表來存儲合併後的區間。

3. 追踪區間：

   • 對於每個當前區間，檢查它是否與合併列表中的最後一個區間重疊。
   • 如果不重疊，則將當前區間添加到合併列表中。
   • 如果重疊，則更新合併列表中最後一個區間的結束時間，將其與當前區間的結束時間取最大值。

4. 返回合併後的列表：最後返回合併後的區間列表。

實作

def merge_intervals(intervals):
    if not intervals:
        return []
    
    # 步驟 1：根據開始時間對區間進行排序
    intervals.sort(key=lambda x: x[0])
    
    # 步驟 2：初始化合併列表
    merged = []
    
    # 步驟 3：追踪區間
    for current in intervals:
        # 如果合併列表為空或沒有重疊，則添加當前區間
        if not merged or merged[-1][1] < current[0]:
            merged.append(current)
        else:
            # 有重疊，合併當前區間
            merged[-1][1] = max(merged[-1][1], current[1])
    
    return merged

# 範例使用
arr1 = [[1, 3], [2, 4], [6, 8], [9, 10]]
arr2 = [[6, 8], [1, 9], [2, 4], [4, 7]]

print(merge_intervals(arr1))  # 輸出: [[1, 4], [6, 8], [9, 10]]
print(merge_intervals(arr2))  # 輸出: [[1, 9]]

代碼解釋

1. 排序：使用 sort 函數根據開始時間對區間進行排序。
2. 合併邏輯：
   • 檢查合併列表是否為空，或合併列表中最後一個區間的結束時間是否小於當前區間的開始時間。
   • 如果有重疊，則更新合併列表中最後一個區間的結束時間為兩個重疊區間的最大結束時間。
3. 輸出：函數返回合併後的區間列表。

時間複雜度

• 排序：(O(n \log n))，其中 (n) 是區間的數量。
• 合併：(O(n))，因為每個區間只處理一次。

因此，整體時間複雜度為 (O(n \log n))，空間複雜度為 (O(n))，用於存儲合併後的區間。

參考資料：https://www.geeksforgeeks.org/merging-intervals/

計算從二元樹的根節點到所有葉子節點的路徑數字的總和

 

問題

實現一個函數 find_sum_of_path_numbers，用來計算從二元樹的根節點到所有葉子節點的路徑數字的總和。每條路徑的數字由沿途的節點值組成。

程式碼實現

以下是 find_sum_of_path_numbers 函數及其輔助函數的實現：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def find_sum_of_path_numbers(root):
    return find_root_to_leaf_path_numbers(root, 0)

def find_root_to_leaf_path_numbers(current_node, path_sum):
    if current_node is None:
        return 0
      
    # 計算當前路徑數字
    path_sum = 10 * path_sum + current_node.val
    
    # 如果是葉子節點，返回當前路徑數字
    if current_node.left is None and current_node.right is None:
        return path_sum
      
    # 遞歸計算左子樹和右子樹的路徑數字總和
    return (find_root_to_leaf_path_numbers(current_node.left, path_sum) + 
            find_root_to_leaf_path_numbers(current_node.right, path_sum))

測試範例

以下是如何建立一棵簡單的二叉樹並測試 find_sum_of_path_numbers 函數：

def main():
    # 建立範例二叉樹：
    #       1
    #      / \
    #     0   1
    #    / \   \
    #   1   1   1

    root = TreeNode(1)
    root.left = TreeNode(0)
    root.right = TreeNode(1)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(1)
    root.right.right = TreeNode(1)

    # 計算從根到葉子的路徑數字的總和
    result = find_sum_of_path_numbers(root)
    print(result)  # 預期輸出：312 (101 + 101 + 111)

if __name__ == "__main__":
    main()

測試案例解釋

在這個範例中，樹的結構如下：

      1
     / \
    0   1
   / \   \
  1   1   1

從根到葉子的路徑數字如下：

1. 路徑 1 → 0 → 1 形成數字 101
2. 路徑 1 → 0 → 1 形成數字 101
3. 路徑 1 → 1 → 1 形成數字 111

因此，所有路徑數字的總和是 101 + 101 + 111 = 313。

你可以運行這段程式碼來驗證結果。如果有任何問題或需要進一步的解釋，請隨時告訴我！

資料來源：
https://hackmd.io/@Hsins/depth-first-search

檢查一棵二元樹中是否存在一條從根節點到葉子節點的路徑

 

問題

請用 Python 實現一個函數 has_path，用來檢查一棵二元樹中是否存在一條從根節點到葉子節點的路徑，使得該路徑上所有節點的值之和等於給定的目標值。請提供一個簡單的二元樹結構，以及一些範例測試用例。

解答

以下是 has_path 函數的實現和測試用例：

TreeNode 類別定義

首先，我們定義一個 TreeNode 類別來表示二叉樹的節點：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

has_path 函數實現

接下來，這是 has_path 函數的實現：

def has_path(root, target):
    if root is None:
        return False
      
    # 檢查是否為葉子節點且其值等於目標
    if root.val == target and root.left is None and root.right is None:
        return True
      
    # 遞歸檢查左子樹和右子樹
    return has_path(root.left, target - root.val) or has_path(root.right, target - root.val)

測試用例

以下是如何創建範例樹並測試 has_path 函數：

def main():
    # 建立一個範例二叉樹：
    #       5
    #      / \
    #     4   8
    #    /   / \
    #   11  13  4
    #   / \      \
    #  7   2      1

    root = TreeNode(5)
    root.left = TreeNode(4)
    root.right = TreeNode(8)
    root.left.left = TreeNode(11)
    root.left.left.left = TreeNode(7)
    root.left.left.right = TreeNode(2)
    root.right.left = TreeNode(13)
    root.right.right = TreeNode(4)
    root.right.right.right = TreeNode(1)

    # 測試案例
    print(has_path(root, 22))  # 預期輸出：True (5 -> 4 -> 11 -> 2)
    print(has_path(root, 26))  # 預期輸出：True (5 -> 8 -> 13)
    print(has_path(root, 18))  # 預期輸出：True (5 -> 8 -> 4 -> 1)
    print(has_path(root, 27))  # 預期輸出：False (沒有這樣的路徑)
    print(has_path(root, 10))  # 預期輸出：False (沒有這樣的路徑)

if __name__ == "__main__":
    main()

測試案例解釋

1. has_path(root, 22)：路徑 5 → 4 → 11 → 2 的和是 22，因此返回 True。
2. has_path(root, 26)：路徑 5 → 8 → 13 的和是 26，因此返回 True。
3. has_path(root, 18)：路徑 5 → 8 → 4 → 1 的和是 18，因此返回 True。
4. has_path(root, 27)：沒有任何路徑的和是 27，因此返回 False。
5. has_path(root, 10)：也沒有任何路徑的和是 10，因此返回 False。

資料來源：
https://hackmd.io/@Hsins/depth-first-search