1
2023-09-03：用 go 编写。给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ， 其中 edges[i] =
作者：福大大架构师每日一题
- 2023-09-03 北京
本文字数：4372 字
阅读完需：约 14 分钟
2023-09-03：用 go 语言编写。给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1
给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，
其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。
再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，
1 表示节点 i 处有一个金币。
一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：
收集距离当前节点距离为 2 以内的所有金币，或者 移动到树中一个相邻节点。
你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。
如果你多次经过一条边，每一次经过都会给答案加一。
输入：coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]。
输出：2。
来自左程云。
答案 2023-09-03：
代码思路：
1.创建图结构和入度数组，并初始化空图和入度数组。
2.遍历边数组，将边的两个节点加入图中，同时更新入度数组。
3.创建队列，并将所有入度为 1 且节点上金币为 0 的节点加入队列。
4.使用 BFS 算法遍历队列，将入度-1 并将入度为 1 且节点上金币为 0 的相邻节点加入队列。
5.继续遍历队列，将入度-1 并记录节点的排名，并将入度为 1 的相邻节点加入队列。
6.计算满足条件的边数，即排名大于等于 2 的边。
7.返回计数值作为最少经过的边数。
总的时间复杂度：O(n)，其中 n 为节点数量，需要遍历边数组和节点数组，同时进行 BFS 操作。
总的额外空间复杂度：O(n)，需要创建图结构、入度数组和队列。
go 完整代码如下：
package main
import "fmt"
func collectTheCoins(coins []int, edges [][]int) int { n := len(coins) graph := make([][]int, n) inDegree := make([]int, n)
for i := 0; i < n; i++ { graph[i] = []int{} }
for _, edge := range edges { graph[edge[0]] = append(graph[edge[0]], edge[1]) graph[edge[1]] = append(graph[edge[1]], edge[0]) inDegree[edge[0]]++ inDegree[edge[1]]++ }
queue := make([]int, n) l, r := 0, 0
for i := 0; i < n; i++ { if inDegree[i] == 1 && coins[i] == 0 { queue[r] = i r++ } }
for l < r { cur := queue[l] l++ for _, next := range graph[cur] { if inDegree[next]--; inDegree[next] == 1 && coins[next] == 0 { queue[r] = next r++ } } }
for i := 0; i < n; i++ { if inDegree[i] == 1 && coins[i] == 1 { queue[r] = i r++ } }
rank := make([]int, n)
for l < r { cur := queue[l] l++ for _, next := range graph[cur] { if inDegree[next]--; inDegree[next] == 1 { rank[next] = rank[cur] + 1 queue[r] = next r++ } } }
ans := 0
for _, edge := range edges { if rank[edge[0]] >= 2 && rank[edge[1]] >= 2 { ans += 2 } }
return ans}
func main() { coins := []int{1, 0, 0, 0, 0, 1} edges := [][]int{{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}}
result := collectTheCoins(coins, edges) fmt.Println(result)}
复制代码
rust 完整代码如下：
fn collect_the_coins(coins: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 { let n = coins.len(); let mut graph: Vec<Vec<i32>> = vec![vec![]; n]; let mut in_degree: Vec<i32> = vec![0; n];
for edge in &edges { let u = edge[0]; let v = edge[1]; graph[u as usize].push(v); graph[v as usize].push(u); in_degree[u as usize] += 1; in_degree[v as usize] += 1; }
let mut queue: Vec<i32> = vec![0; n]; let mut l = 0; let mut r = 0; for i in 0..n { if in_degree[i] == 1 && coins[i] == 0 { queue[r as usize] = i as i32; r += 1; } }
while l < r { let cur = queue[l as usize]; l += 1; for &next in &graph[cur as usize] { in_degree[next as usize] -= 1; if in_degree[next as usize] == 1 && coins[next as usize] == 0 { queue[r as usize] = next; r += 1; } } }
for i in 0..n { if in_degree[i] == 1 && coins[i] == 1 { queue[r as usize] = i as i32; r += 1; } }
let mut rank: Vec<i32> = vec![0; n]; while l < r { let cur = queue[l as usize] as usize; l += 1; for &next in &graph[cur] { in_degree[next as usize] -= 1; if in_degree[next as usize] == 1 { rank[next as usize] = rank[cur] + 1; queue[r as usize] = next; r += 1; } } }
let mut ans = 0; for edge in &edges { let u = edge[0] as usize; let v = edge[1] as usize; if rank[u] >= 2 && rank[v] >= 2 { ans += 2; } }
ans}
fn main() { let coins = vec![0, 0, 0, 1, 1, 0, 0, 1]; let edges = vec![ vec![0, 1], vec![0, 2], vec![1, 3], vec![1, 4], vec![2, 5], vec![5, 6], vec![5, 7], ];
let result = collect_the_coins(coins, edges); println!("Result: {}", result);}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>
using namespace std;
int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) { int n = coins.size(); vector<vector<int>> graph(n); vector<int> inDegree(n, 0); for (auto& edge : edges) { graph[edge[0]].push_back(edge[1]); graph[edge[1]].push_back(edge[0]); inDegree[edge[0]]++; inDegree[edge[1]]++; } vector<int> queue; int l = 0, r = 0; for (int i = 0; i < n; ++i) { if (inDegree[i] == 1 && coins[i] == 0) { queue.push_back(i); r++; } } while (l < r) { int cur = queue[l++]; for (int next : graph[cur]) { if (--inDegree[next] == 1 && coins[next] == 0) { queue.push_back(next); r++; } } } for (int i = 0; i < n; ++i) { if (inDegree[i] == 1 && coins[i] == 1) { queue.push_back(i); r++; } } vector<int> rank(n, 0); while (l < r) { int cur = queue[l++]; for (int next : graph[cur]) { if (--inDegree[next] == 1) { rank[next] = rank[cur] + 1; queue.push_back(next); r++; } } } int ans = 0; for (auto& edge : edges) { if (rank[edge[0]] >= 2 && rank[edge[1]] >= 2) { ans += 2; } } return ans;}
int main() { vector<int> coins = { 1, 0, 0, 0, 0, 1 }; vector<vector<int>> edges = { {0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5} };
int result = collectTheCoins(coins, edges); cout << result << endl;
return 0;}
复制代码
c 完整代码如下：
#include <stdio.h>#include <stdlib.h>
int collectTheCoins(int* coins, int coinsSize, int** edges, int edgesSize, int* edgesColSize) { int n = coinsSize; int** graph = (int**)malloc(n * sizeof(int*)); int* inDegree = (int*)calloc(n, sizeof(int));
for (int i = 0; i < n; i++) { graph[i] = (int*)malloc(n * sizeof(int)); }
for (int i = 0; i < edgesSize; i++) { int v = edges[i][0]; int u = edges[i][1]; graph[v][u] = 1; graph[u][v] = 1; inDegree[v]++; inDegree[u]++; }
int* queue = (int*)malloc(n * sizeof(int)); int l = 0, r = 0; for (int i = 0; i < n; ++i) { if (inDegree[i] == 1 && coins[i] == 0) { queue[r++] = i; } }
while (l < r) { int cur = queue[l++]; for (int next = 0; next < n; next++) { if (graph[cur][next] == 1) { if (--inDegree[next] == 1 && coins[next] == 0) { queue[r++] = next; } } } }
for (int i = 0; i < n; ++i) { if (inDegree[i] == 1 && coins[i] == 1) { queue[r++] = i; } }
int* rank = (int*)calloc(n, sizeof(int)); while (l < r) { int cur = queue[l++]; for (int next = 0; next < n; next++) { if (graph[cur][next] == 1) { if (--inDegree[next] == 1) { rank[next] = rank[cur] + 1; queue[r++] = next; } } } }
int ans = 0; for (int i = 0; i < edgesSize; i++) { if (rank[edges[i][0]] >= 2 && rank[edges[i][1]] >= 2) { ans += 2; } }
// 释放动态分配的内存 for (int i = 0; i < n; i++) { free(graph[i]); } free(graph); free(inDegree); free(queue); free(rank);
return ans;}
int main() { int coins[] = { 1, 0, 0, 0, 0, 1 }; int* edges[] = { (int[]) {0, 1}, (int[]) {1, 2}, (int[]) {2, 3}, (int[]) {3, 4}, (int[]) {4, 5} }; int coinsSize = sizeof(coins) / sizeof(coins[0]); int edgesSize = sizeof(edges) / sizeof(edges[0]); int edgesColSize[] = { 2, 2, 2, 2, 2 };
int result = collectTheCoins(coins, coinsSize, edges, edgesSize, edgesColSize); printf("Result: %d\n", result);
return 0;}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 5
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/ab1cb393067052e75d4ebba77】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
福大大架构师每日一题
关注
公众号：福大大架构师每日一题 2021-02-15 加入
公众号：福大大架构师每日一题
![2023-09-03：用go编写。给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ， 其中 edges[i] =_福大大架构师每日一题_福大大架构师每日一题_InfoQ写作社区](https://static001.infoq.cn/static/infoq/img/logo-121-75.yuij86g.png){kind=logo}
评论