【每日一题Day333】LC2603收集树中金币 | 拓扑排序

简介: 【每日一题Day333】LC2603收集树中金币 | 拓扑排序

收集树中金币【LC2603】

给你一个 n 个节点的无向无根树,节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ,其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ,其中 coins[i] 可能为 0 也可能为 1 ,1 表示节点 i 处有一个金币。

一开始,你需要选择树中任意一个节点出发。你可以执行下述操作任意次:

收集距离当前节点距离为 2 以内的所有金币,或者

移动到树中一个相邻节点。

你需要收集树中所有的金币,并且回到出发节点,请你返回最少经过的边数。

如果你多次经过一条边,每一次经过都会给答案加一。

思路:拓扑排序+贪心

首先,我们可以去掉不包含金币的子树【步骤a】,因为访问其中任何一个点都毫无意义。

实现:拓扑排序,去除不含金币的叶子节点

如果所有在叶子上的金币全部都能收集到,那么我们可以收集到树上所有金币。而由于可以「收集距离当前节点距离为 2以内的所有金币」,因此可以再次去除两轮有金币的叶子【步骤b】,剩余的结点即为必须经过的结点

贪心:从距离有金币叶子为2的节点处出发【局部最优】,收集树中所有的金币,并且回到出发节点时经过的边数最少【全局最优】。

实现:再次进行拓扑排序

最终答案:从某个节点出发后,仍需要回到起点;因此最终答案为剩余边数乘以2。

实现1:统计每个必须经过的节点的入队时间,如果一条边的两个节点的入队时间均大于2,那么这条边必须经过两次

实现2:在拓扑排序时记录不需要遍历的边的数目【步骤a和步骤b的边数】,最后需要进行特判,如果所有节点均需要删除时,答案为-1,此时应与0取较大值

实现

无向图,节点度为1时为叶子

class Solution {
    public int collectTheCoins(int[] coins, int[][] edges) {
        int n = coins.length;
        List<Integer> g[] = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        var deg = new int[n];
        for (var e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x); // 建图
            ++deg[x];
            ++deg[y];
        }
        // 用拓扑排序「剪枝」:去掉没有金币的子树
        var q = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i)
            if (deg[i] == 1 && coins[i] == 0) // 无金币叶子
                q.add(i);
        while (!q.isEmpty()) {
            int x = q.peek();
            q.pop();
            for (int y : g[x])
                if (--deg[y] == 1 && coins[y] == 0)// 无金币叶子
                    q.add(y);
        }
        // 再次拓扑排序
        for (int i = 0; i < n; ++i)
            if (deg[i] == 1 && coins[i] == 1) // 有金币叶子
                q.add(i);
        if (q.size() <= 1) return 0; // 至多一个有金币的叶子,直接收集
        var time = new int[n];
        while (!q.isEmpty()) {
            int x = q.peek();
            q.pop();
            for (int y : g[x])
                if (--deg[y] == 1) {
                    time[y] = time[x] + 1; // 记录入队时间
                    q.add(y);
                }
        }
        // 统计答案
        int ans = 0;
        for (var e : edges)
            if (time[e[0]] >= 2 && time[e[1]] >= 2)
                ans += 2;
        return ans;
    }
}
作者:灵茶山艾府
链接:https://leetcode.cn/problems/collect-coins-in-a-tree/solutions/2191371/tuo-bu-pai-xu-ji-lu-ru-dui-shi-jian-pyth-6uli/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

复杂度

时间复杂度:O ( E + V ) ,E表示邻边的跳数,V为结点的个数

空间复杂度:O ( V )

实现2

class Solution {
    public int collectTheCoins(int[] coins, int[][] edges) {
        int n = coins.length;
        List<Integer> g[] = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        var deg = new int[n];
        for (var e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x); // 建图
            deg[x]++;
            deg[y]++; // 统计每个节点的度数(邻居个数)
        }
        int leftEdges = n - 1; // 剩余边数
        // 拓扑排序,去掉没有金币的子树
        var q = new ArrayDeque<Integer>();
        for (int i = 0; i < n; i++) {
            if (deg[i] == 1 && coins[i] == 0) { // 没有金币的叶子
                q.add(i);
            }
        }
        while (!q.isEmpty()) {
            leftEdges--; // 删除节点到其父节点的边
            for (int y : g[q.poll()]) {
                if (--deg[y] == 1 && coins[y] == 0) { // 没有金币的叶子
                    q.add(y);
                }
            }
        }
        // 再次拓扑排序
        for (int i = 0; i < n; i++) {
            if (deg[i] == 1 && coins[i] == 1) { // 有金币的叶子(判断 coins[i] 是避免把没有金币的叶子也算进来)
                q.add(i);
            }
        }
        leftEdges -= q.size(); // 删除所有叶子(到其父节点的边)
        for (int x : q) { // 遍历所有叶子
            for (int y : g[x]) {
                if (--deg[y] == 1) { // y 现在是叶子了
                    leftEdges--; // 删除 y(到其父节点的边)
                }
            }
        }
        return Math.max(leftEdges * 2, 0);
    }
}
作者:灵茶山艾府
链接:https://leetcode.cn/problems/collect-coins-in-a-tree/solutions/2191371/tuo-bu-pai-xu-ji-lu-ru-dui-shi-jian-pyth-6uli/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

复杂度


时间复杂度:O ( E + V ) ,E表示邻边的跳数,V为结点的个数

空间复杂度:O ( V )

  • 升级:如果把题目中的 2 换成 0,1,2,3,⋯ ,n−1,你能把这些情况对应的答案全部算出来吗?
    遍历所有的边,如果两个节点的入队时间均大于q(最大距离),那么表示这条边必须要经过,结果+2
目录
相关文章
|
7月前
|
算法 vr&ar 图形学
☆打卡算法☆LeetCode 222. 完全二叉树的节点个数 算法解析
☆打卡算法☆LeetCode 222. 完全二叉树的节点个数 算法解析
|
7月前
|
人工智能 BI
【每日一题Day267】LC834树中距离之和 | 换根dp
【每日一题Day267】LC834树中距离之和 | 换根dp
46 0
|
7月前
【每日一题Day305】LC1448统计二叉树中好节点的数目 | dfs
【每日一题Day305】LC1448统计二叉树中好节点的数目 | dfs
42 0
|
7月前
|
人工智能 BI
【每日一题Day232】LC2699修改图中的边权 |最短路径
【每日一题Day232】LC2699修改图中的边权 |最短路径
39 0
|
7月前
|
人工智能 BI
【每日一题Day354】LC2316统计无向图中无法互相到达点对数 | 并查集
【每日一题Day354】LC2316统计无向图中无法互相到达点对数 | 并查集
57 0
|
6月前
|
算法 C++
【洛谷 P1090】[NOIP2004 提高组] 合并果子(贪心算法+哈夫曼编码+优先队列)
该编程题目要求设计算法,将不同种类的果子合并成一堆,使得消耗的体力最小。给定果子种类数`n`(1至10000)和每种果子的数量,需输出合并的最小体力值。使用优先队列(最小堆),每次取出两个数量最少的果子堆合并,并更新总体力消耗。样例输入为3种果子(1, 2, 9),输出最小体力耗费为15。提供的AC代码采用C++实现,通过优先队列优化合并顺序。
76 0
|
7月前
|
人工智能 算法 BI
【图论】【树】 【拓扑排序】2603. 收集树中金币
【图论】【树】 【拓扑排序】2603. 收集树中金币
|
7月前
|
vr&ar
【每日一题Day166】LC1053交换一次的先前排列 | 贪心
【每日一题Day166】LC1053交换一次的先前排列 | 贪心
72 1
|
7月前
|
存储 算法
【每日一题Day310】LC1654到家的最少跳跃次数 | BFS
【每日一题Day310】LC1654到家的最少跳跃次数 | BFS
45 0
|
7月前
【每日一题Day265】LC979在二叉树中分配硬币 | 树形dp
【每日一题Day265】LC979在二叉树中分配硬币 | 树形dp
56 0