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完整代码如下：

packagemainimport"fmt"funccollectTheCoins(coins[]int,edges[][]int)int{n:=len(coins)graph:=make([][]int,n)inDegree:=make([]int,n)fori:=0;igraph[i]=[]int{}}for_,edge:=rangeedges{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,0fori:=0;iifinDegree[i]==1&&coins[i]==0{queue[r]=ir++}}forlcur:=queue[l]l++for_,next:=rangegraph[cur]{ifinDegree[next]--;inDegree[next]==1&&coins[next]==0{queue[r]=nextr++}}}fori:=0;iifinDegree[i]==1&&coins[i]==1{queue[r]=ir++}}rank:=make([]int,n)forlcur:=queue[l]l++for_,next:=rangegraph[cur]{ifinDegree[next]--;inDegree[next]==1{rank[next]=rank[cur]+1queue[r]=nextr++}}}ans:=0for_,edge:=rangeedges{ifrank[edge[0]]>=2&&rank[edge[1]]>=2{ans+=2}}returnans}funcmain(){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完整代码如下：

fncollect_the_coins(coins:Vec,edges:Vec>)->i32{letn=coins.len();letmutgraph:Vec>=vec![vec![];n];letmutin_degree:Vec=vec![0;n];foredgein&edges{letu=edge[0];letv=edge[1];graph[uasusize].push(v);graph[vasusize].push(u);in_degree[uasusize]+=1;in_degree[vasusize]+=1;}letmutqueue:Vec=vec![0;n];letmutl=0;letmutr=0;foriin0..n{ifin_degree[i]==1&&coins[i]==0{queue[rasusize]=iasi32;r+=1;}}whilelletcur=queue[lasusize];l+=1;for&nextin&graph[curasusize]{in_degree[nextasusize]-=1;ifin_degree[nextasusize]==1&&coins[nextasusize]==0{queue[rasusize]=next;r+=1;}}}foriin0..n{ifin_degree[i]==1&&coins[i]==1{queue[rasusize]=iasi32;r+=1;}}letmutrank:Vec=vec![0;n];whilelletcur=queue[lasusize]asusize;l+=1;for&nextin&graph[cur]{in_degree[nextasusize]-=1;ifin_degree[nextasusize]==1{rank[nextasusize]=rank[cur]+1;queue[rasusize]=next;r+=1;}}}letmutans=0;foredgein&edges{letu=edge[0]asusize;letv=edge[1]asusize;ifrank[u]>=2&&rank[v]>=2{ans+=2;}}ans}fnmain(){letcoins=vec![0,0,0,1,1,0,0,1];letedges=vec![vec![0,1],vec![0,2],vec![1,3],vec![1,4],vec![2,5],vec![5,6],vec![5,7],];letresult=collect_the_coins(coins,edges);println!("Result:{}",result);}

c++完整代码如下：

#include#includeusingnamespacestd;intcollectTheCoins(vector&coins,vector>&edges){intn=coins.size();vector>graph(n);vectorinDegree(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]]++;}vectorqueue;intl=0,r=0;for(inti=0;iif(inDegree[i]==1&&coins[i]==0){queue.push_back(i);r++;}}while(lintcur=queue[l++];for(intnext:graph[cur]){if(--inDegree[next]==1&&coins[next]==0){queue.push_back(next);r++;}}}for(inti=0;iif(inDegree[i]==1&&coins[i]==1){queue.push_back(i);r++;}}vectorrank(n,0);while(lintcur=queue[l++];for(intnext:graph[cur]){if(--inDegree[next]==1){rank[next]=rank[cur]+1;queue.push_back(next);r++;}}}intans=0;for(auto&edge:edges){if(rank[edge[0]]>=2&&rank[edge[1]]>=2){ans+=2;}}returnans;}intmain(){vectorcoins={1,0,0,0,0,1};vector>edges={{0,1},{1,2},{2,3},{3,4},{4,5}};intresult=collectTheCoins(coins,edges);cout<return0;}

c完整代码如下：

#include#includeintcollectTheCoins(int*coins,intcoinsSize,int**edges,intedgesSize,int*edgesColSize){intn=coinsSize;int**graph=(int**)malloc(n*sizeof(int*));int*inDegree=(int*)calloc(n,sizeof(int));for(inti=0;igraph[i]=(int*)malloc(n*sizeof(int));}for(inti=0;iintv=edges[i][0];intu=edges[i][1];graph[v][u]=1;graph[u][v]=1;inDegree[v]++;inDegree[u]++;}int*queue=(int*)malloc(n*sizeof(int));intl=0,r=0;for(inti=0;iif(inDegree[i]==1&&coins[i]==0){queue[r++]=i;}}while(lintcur=queue[l++];for(intnext=0;nextif(graph[cur][next]==1){if(--inDegree[next]==1&&coins[next]==0){queue[r++]=next;}}}}for(inti=0;iif(inDegree[i]==1&&coins[i]==1){queue[r++]=i;}}int*rank=(int*)calloc(n,sizeof(int));while(lintcur=queue[l++];for(intnext=0;nextif(graph[cur][next]==1){if(--inDegree[next]==1){rank[next]=rank[cur]+1;queue[r++]=next;}}}}intans=0;for(inti=0;iif(rank[edges[i][0]]>=2&&rank[edges[i][1]]>=2){ans+=2;}}//释放动态分配的内存for(inti=0;ifree(graph[i]);}free(graph);free(inDegree);free(queue);free(rank);returnans;}intmain(){intcoins[]={1,0,0,0,0,1};int*edges[]={(int[]){0,1},(int[]){1,2},(int[]){2,3},(int[]){3,4},(int[]){4,5}};intcoinsSize=sizeof(coins)/sizeof(coins[0]);intedgesSize=sizeof(edges)/sizeof(edges[0]);intedgesColSize[]={2,2,2,2,2};intresult=collectTheCoins(coins,coinsSize,edges,edgesSize,edgesColSize);printf("Result:%d\n",result);return0;}