2023-09-03：用go編寫。給你一個(gè) n 個(gè)節(jié)點(diǎn)的無向無根樹，節(jié)點(diǎn)編號從 0 到 n - 1 給你
2023-09-03：用go語言編寫。給你一個(gè) n 個(gè)節(jié)點(diǎn)的無向無根樹，節(jié)點(diǎn)編號從 0 到 n - 1
給你整數(shù) n 和一個(gè)長度為 n - 1 的二維整數(shù)數(shù)組 edges ，
其中 edges[i] = [ai, bi] 表示樹中節(jié)點(diǎn) ai 和 bi 之間有一條邊。
再給你一個(gè)長度為 n 的數(shù)組 coins ，其中 coins[i] 可能為 0 也可能為 1 ，
1 表示節(jié)點(diǎn) i 處有一個(gè)金幣。
一開始，你需要選擇樹中任意一個(gè)節(jié)點(diǎn)出發(fā)。你可以執(zhí)行下述操作任意次：
收集距離當(dāng)前節(jié)點(diǎn)距離為 2 以內(nèi)的所有金幣，或者 移動(dòng)到樹中一個(gè)相鄰節(jié)點(diǎn)。
你需要收集樹中所有的金幣，并且回到出發(fā)節(jié)點(diǎn)，請你返回最少經(jīng)過的邊數(shù)。
如果你多次經(jīng)過一條邊，每一次經(jīng)過都會(huì)給答案加一。
輸入：coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]。
輸出：2。
來自左程云。
答案2023-09-03：
代碼思路：
1.創(chuàng)建圖結(jié)構(gòu)和入度數(shù)組，并初始化空圖和入度數(shù)組。
2.遍歷邊數(shù)組，將邊的兩個(gè)節(jié)點(diǎn)加入圖中，同時(shí)更新入度數(shù)組。
3.創(chuàng)建隊(duì)列，并將所有入度為1且節(jié)點(diǎn)上金幣為0的節(jié)點(diǎn)加入隊(duì)列。
4.使用BFS算法遍歷隊(duì)列，將入度-1并將入度為1且節(jié)點(diǎn)上金幣為0的相鄰節(jié)點(diǎn)加入隊(duì)列。
5.繼續(xù)遍歷隊(duì)列，將入度-1并記錄節(jié)點(diǎn)的排名，并將入度為1的相鄰節(jié)點(diǎn)加入隊(duì)列。
6.計(jì)算滿足條件的邊數(shù)，即排名大于等于2的邊。
7.返回計(jì)數(shù)值作為最少經(jīng)過的邊數(shù)。
總的時(shí)間復(fù)雜度：O(n)，其中n為節(jié)點(diǎn)數(shù)量，需要遍歷邊數(shù)組和節(jié)點(diǎn)數(shù)組，同時(shí)進(jìn)行BFS操作。
總的額外空間復(fù)雜度：O(n)，需要?jiǎng)?chuàng)建圖結(jié)構(gòu)、入度數(shù)組和隊(duì)列。
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++完整代碼如下：
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完整代碼如下：
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;
????????}
????}
????//?釋放動(dòng)態(tài)分配的內(nèi)存
????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;
}
