Hard

题目描述

存在一个无向且无根的树，有 n 个节点，节点编号从 0 到 n - 1。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。你还会得到一个大小为 n 的数组 coins，其中 coins[i] 可以是 0 或 1，其中 1 表示顶点 i 处有一枚金币。

最初，你可以选择从树中的任何顶点开始。然后，你可以执行以下操作任意次数：

  • 收集距离当前顶点最多为 2 的所有金币，或
  • 移动到树中的任何相邻顶点。

找出收集所有金币并返回初始顶点所需要经过的最少边数。

注意，如果你多次经过一条边，你需要将其多次计入答案中。

示例 1：

输入：coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：从顶点 2 开始，收集顶点 0 处的金币，移动到顶点 3，收集顶点 5 处的金币，然后移回顶点 2。

示例 2：

输入：coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]
输出：2
解释：从顶点 0 开始，收集顶点 4 和 3 处的金币，移动到顶点 2，收集顶点 7 处的金币，然后移回顶点 0。

提示：

  • n == coins.length
  • 1 <= n <= 3 * 10^4
  • 0 <= coins[i] <= 1
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • edges 表示一个有效的树。

解题思路

这道题的关键思路是通过拓扑排序优化树结构，减少不必要的遍历。

核心观察：

  1. 由于每次可以收集距离当前位置最多2的金币，我们需要找到一条能覆盖所有有金币节点的最短路径
  2. 没有金币的叶子节点是多余的，可以直接删除
  3. 删除无用叶子后，还需要考虑距离因素：如果一个有金币的叶子节点，我们可以在距离它2步的地方收集到，那么我们不需要真正走到那里

算法步骤：

  1. 第一轮拓扑排序：删除所有没有金币的叶子节点，直到所有叶子都有金币或只剩1-2个节点
  2. 第二轮拓扑排序：由于可以在距离2的地方收集金币，我们可以进一步删除2轮叶子节点（包括有金币的叶子）
  3. 计算答案：剩余的节点就是我们必须访问的节点，答案是 (剩余节点数 - 1) × 2

这个算法的精妙之处在于：通过两轮删除，我们得到的是一个最小的连通子图，遍历这个子图并返回起点的路径长度就是答案。由于是树结构，遍历 k 个节点并返回需要走 2(k-1) 条边。

代码实现

class Solution {
public:
    int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
        int n = coins.size();
        if (n <= 2) return 0;
        
        // 建图
        vector<vector<int>> graph(n);
        vector<int> degree(n, 0);
        
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
            degree[edge[0]]++;
            degree[edge[1]]++;
        }
        
        vector<bool> removed(n, false);
        
        // 第一轮：删除没有金币的叶子节点
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1 && coins[i] == 0) {
                q.push(i);
            }
        }
        
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            removed[node] = true;
            
            for (int neighbor : graph[node]) {
                if (!removed[neighbor]) {
                    degree[neighbor]--;
                    if (degree[neighbor] == 1 && coins[neighbor] == 0) {
                        q.push(neighbor);
                    }
                }
            }
        }
        
        // 第二轮：删除2轮叶子节点（考虑距离为2的收集能力）
        for (int round = 0; round < 2; round++) {
            for (int i = 0; i < n; i++) {
                if (!removed[i] && degree[i] == 1) {
                    q.push(i);
                }
            }
            
            while (!q.empty()) {
                int node = q.front();
                q.pop();
                removed[node] = true;
                
                for (int neighbor : graph[node]) {
                    if (!removed[neighbor]) {
                        degree[neighbor]--;
                    }
                }
            }
        }
        
        // 计算剩余节点数
        int remaining = 0;
        for (int i = 0; i < n; i++) {
            if (!removed[i]) {
                remaining++;
            }
        }
        
        return remaining <= 1 ? 0 : (remaining - 1) * 2;
    }
};

class Solution:
    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:
        n = len(coins)
        if n <= 2:
            return 0
        
        # 建图
        graph = [[] for _ in range(n)]
        degree = [0] * n
        
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
            degree[a] += 1
            degree[b] += 1
        
        removed = [False] * n
        
        # 第一轮：删除没有金币的叶子节点
        q = deque()
        for i in range(n):
            if degree[i] == 1 and coins[i] == 0:
                q.append(i)
        
        while q:
            node = q.popleft()
            removed[node] = True
            
            for neighbor in graph[node]:
                if not removed[neighbor]:
                    degree[neighbor] -= 1
                    if degree[neighbor] == 1 and coins[neighbor] == 0:
                        q.append(neighbor)
        
        # 第二轮：删除2轮叶子节点
        for _ in range(2):
            leaves = []
            for i in range(n):
                if not removed[i] and degree[i] == 1:
                    leaves.append(i)
            
            for node in leaves:
                removed[node] = True
                for neighbor in graph[node]:
                    if not removed[neighbor]:
                        degree[neighbor] -= 1
        
        # 计算剩余节点数
        remaining = sum(1 for i in range(n) if not removed[i])
        
        return 0 if remaining <= 1 else (remaining - 1) * 2

public class Solution {
    public int CollectTheCoins(int[] coins, int[][] edges) {
        int n = coins.Length;
        if (n <= 2) return 0;
        
        // 建图
        List<int>[] graph = new List<int>[n];
        int[] degree = new int[n];
        
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
            degree[edge[0]]++;
            degree[edge[1]]++;
        }
        
        bool[] removed = new bool[n];
        
        // 第一轮：删除没有金币的叶子节点
        Queue<int> q = new Queue<int>();
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1 && coins[i] == 0) {
                q.Enqueue(i);
            }
        }
        
        while (q.Count > 0) {
            int node = q.Dequeue();
            removed[node] = true;
            
            foreach (int neighbor in graph[node]) {
                if (!removed[neighbor]) {
                    degree[neighbor]--;
                    if (degree[neighbor] == 1 && coins[neighbor] == 0) {
                        q.Enqueue(neighbor);
                    }
                }
            }
        }
        
        // 第二轮：删除2轮叶子节点
        for (int round = 0; round < 2; round++) {
            List<int> leaves = new List<int>();
            for (int i = 0; i < n; i++) {
                if (!removed[i] && degree[i] == 1) {
                    leaves.Add(i);
                }
            }
            
            foreach (int node in leaves) {
                removed[node] = true;
                foreach (int neighbor in graph[node]) {
                    if (!removed[neighbor]) {
                        degree[neighbor]--;
                    }
                }
            }
        }
        
        // 计算剩余节点数
        int remaining = 0;
        for (int i = 0; i < n; i++) {
            if (!removed[i]) {
                remaining++;
            }
        }
        
        return remaining <= 1 ? 0 : (remaining - 1) * 2;
    }
}

var collectTheCoins = function(coins, edges) {
    const n = coins.length;
    if (n <= 2) return 0;
    
    // 建图
    const graph = Array.from({length: n}, () => []);
    const degree = new Array(n).fill(0);
    
    for (const [a, b] of edges) {
        graph[a].push(b);
        graph[b].push(a);
        degree[a]++;
        degree[b]++;
    }
    
    const removed = new Array(n).fill(false);
    
    // 第一轮：删除没有金币的叶子节点
    let q = [];
    for (let i = 0; i < n; i++) {
        if (degree[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)每个节点最多被访问常数次，每条边最多被检查常数次
空间复杂度O(n)存储图结构、度数数组和标记数组

相关题目