Skip to content

LeetCode: 1443-Minimum Time to Collect All Apples in a Tree 解題紀錄

Last Updated on 2023-01-11 by Clay

題目

Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend 1 second to walk over one edge of the tree. Return the minimum time in seconds you have to spend to collect all apples in the tree, starting at vertex 0 and coming back to this vertex.

The edges of the undirected tree are given in the array edges, where edges[i] = [ai, bi] means that exists an edge connecting the vertices ai and bi. Additionally, there is a boolean array hasApple, where hasApple[i] = true means that vertex i has an apple; otherwise, it does not have any apple.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
Output: 8 
Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.  

Example 2:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]
Output: 6
Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.  

Example 3:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]
Output: 0

Constraints:

  • 1 <= n <= 105
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai < bi <= n - 1
  • fromi < toi
  • hasApple.length == n

題目會給定一個無向的樹結構,在特定的節點上會存在著蘋果apple)。我們從原點 0 出發,要計算若要收集全部的蘋果,最少的秒數是多少。

每從一個節點走到另外一個節點,都是花一秒。最終我們還需要返回原點 0


解題思路

深度優先搜索

由於題目給定的資料輸入是陣列,所以我會先建立一個 int -> array[int] 的 hash map,key 是節點,value 是節點所連接的其他節點編號組成的陣列。

另外,我也建立了一個 visited 的 hash map,用來記錄已經走過的節點,否則在走 DFS 時,怕會重新走回上一層的節點。

首先自然是把樹狀結構的連結關係用 hash map 儲存起來,接著用 DFS 走訪。每次走訪一個節點時,需要遍歷把連結的所有節點(除了上一層的節點)全部都再次丟入遞迴函式中;最後,如果底下的節點存在著蘋果、或是自身的節點就是蘋果,則在回傳時加上 2

之所以加 2,是因為『走到這個節點』、『走回前一個節點』一定是 2 秒,對於每個節點都是。所以我們只要確認這個節點肯定必須走(底下有蘋果或是自身就有蘋果),就一定得加上 2 秒。

所以最後的答案,一定是『必須走的節點數 x 2』。


DFS 複雜度

Time ComplexityO(n)
Space ComplexityO(n)


C++ 範例程式碼

class Solution {
public:
    int DFS(int vertex, unordered_map<int, vector<int>>& trees, vector<bool>& hasApple, unordered_map<int, bool>& visited) {
        // Init
        int n = 0;

        // We visit the current node, update the `visited`
        visited[vertex] = true;

        // DFS
        for (auto& v: trees[vertex]) {
            if (visited[v]) {
                continue;
            }
            n += DFS(v, trees, hasApple, visited);
        }

        // If there are no any apple and the current node have no apple eigther, return 0
        return n == 0 && !hasApple[vertex] ? 0 : n + 2;
    }
    
    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
        // Init
        unordered_map<int, vector<int>> trees;
        unordered_map<int, bool> visited;
        for (auto& edge: edges) {
            trees[edge[0]].emplace_back(edge[1]);
            trees[edge[1]].emplace_back(edge[0]);
        }

        int num = DFS(0, trees, hasApple, visited);

        return num ? num - 2 : 0;
    }
};



Python 範例程式碼

class Solution:
    def DFS(self, vertex: int, trees: Dict[int, List[int]], hasApple: List[bool], visited: Dict[int, bool]) -> int:
        # Init
        n = 0

        # We visit the current node, update the `visited`
        visited[vertex] = True

        # DFS
        for v in trees[vertex]:
            if (visited.get(v, False)):
                continue
            n += self.DFS(v, trees, hasApple, visited)

        # If there are no any apple and the current node have no apple eigther, return 0
        return 0 if n == 0 and not hasApple[vertex] else n + 2

    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        # Init
        trees = {}
        visited = {}
        for edge in edges:
            trees[edge[0]] = trees.get(edge[0], []) + [edge[1]]
            trees[edge[1]] = trees.get(edge[1], []) + [edge[0]]

        num = self.DFS(0, trees, hasApple, visited)
        return num - 2 if num else 0


References


Read More

Leave a Reply取消回覆

Exit mobile version