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 mainimport "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;}

在这里插入图片描述