岳阳网站优化公司,安陆做网站公司,苏州现代建设公司网站,最新备案域名收集树中金币
力扣链接#xff1a;2603. 收集树中金币
题目描述
给你一个 n 个节点的无向无根树#xff0c;节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges #xff0c;其中 edges[i] [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给…收集树中金币
力扣链接2603. 收集树中金币
题目描述
给你一个 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 。
官解思路 这一步可以使用基于广度优先搜索的拓扑排序解决。我们首先将所有「叶节点」加入队列中随后不断从队列中取出节点将它标记为删除并判断其唯一相邻的节点是否变为「叶节点」。如果是就将相邻的节点也加入队列中。 这一步同样可以使用基于广度优先搜索的拓扑排序解决。我们进行 222 次如下的操作首先将所有「叶节点」加入初始队列中随后不断从初始队列中取出节点将它标记为删除。
Java代码
class Solution {public int collectTheCoins(int[] coins, int[][] edges) {int n coins.length;ListInteger[] g new List[n];for(int i 0; i n; i) {g[i] new ArrayListInteger();}int[] degree new int[n];for(int[] edge : edges) {int x edge[0], y edge[1];g[x].add(y);g[y].add(x);degree[x];degree[y];}int rest n;/* 删除树中所有无金币的叶子节点直到树中所有的叶子节点都是含有金币的 */QueueInteger queue new ArrayDequeInteger();for(int i 0; i n; i) {if(degree[i] 1 coins[i] 0) {queue.offer(i);}}while(!queue.isEmpty()) {int u queue.poll();degree[u]--;rest--;for(int v : g[u]) {degree[v]--;if(degree[v] 1 coins[v] 0) {queue.offer(v);}}}/* 删除树中所有的叶子节点, 连续删除2次 */for(int x 0; x 2; x) {queue new ArrayDequeInteger();for(int i 0; i n; i) {if(degree[i] 1) {queue.offer(i);}}while(!queue.isEmpty()){int u queue.poll();degree[u]--;rest--;for(int v : g[u]) {degree[v]--;}}}return rest 0 ? 0 : (rest - 1) * 2;}
}
