2023-05-05：給定一個(gè)無向、連通的樹 樹中有 n 個(gè)標(biāo)記為 0...n-1 的節(jié)點(diǎn)以及 n-1 條邊
2023-05-05：給定一個(gè)無向、連通的樹
樹中有 n 個(gè)標(biāo)記為 0...n-1 的節(jié)點(diǎn)以及 n-1 條邊 。
給定整數(shù) n 和數(shù)組 edges ，
edges[i] = [ai, bi]表示樹中的節(jié)點(diǎn) ai 和 bi 之間有一條邊。
返回長度為 n 的數(shù)組 answer ，其中 answer[i] :
樹中第 i 個(gè)節(jié)點(diǎn)與所有其他節(jié)點(diǎn)之間的距離之和。
輸入: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]。
輸出: [8,12,6,10,10,10]。
答案2023-05-05：
思路：
給定一棵無向、連通的樹，要求計(jì)算每個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的距離之和。
可以通過遍歷樹，對于每個(gè)節(jié)點(diǎn)分別計(jì)算它到其他節(jié)點(diǎn)的距離之和。對于每個(gè)節(jié)點(diǎn)，利用它的子節(jié)點(diǎn)信息來更新它到其他節(jié)點(diǎn)的距離之和，然后遞歸地更新它的子節(jié)點(diǎn)。最終得到所有節(jié)點(diǎn)的距離之和。
具體實(shí)現(xiàn)如下：
1.構(gòu)造圖
通過給定的?edges?數(shù)組構(gòu)造無向圖。
2.遍歷樹，計(jì)算每個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的距離之和
從根節(jié)點(diǎn)開始遞歸遍歷樹，對于每個(gè)節(jié)點(diǎn)，首先初始化它到其他節(jié)點(diǎn)的距離之和為 0，然后遞歸地處理它的子節(jié)點(diǎn)。處理完所有子節(jié)點(diǎn)之后，計(jì)算該節(jié)點(diǎn)到其他節(jié)點(diǎn)的距離之和，并將該節(jié)點(diǎn)的大小（即包括自身在內(nèi)的節(jié)點(diǎn)數(shù)）保存下來。
3.遞歸更新節(jié)點(diǎn)到其他節(jié)點(diǎn)的距離之和
從根節(jié)點(diǎn)開始遞歸遍歷樹，對于每個(gè)節(jié)點(diǎn)，首先計(jì)算它到其他節(jié)點(diǎn)的距離之和，并將其保存在?ans?數(shù)組中。然后遞歸地處理它的子節(jié)點(diǎn)，將它們對應(yīng)的距離之和更新到?upDistance?中，并計(jì)算每個(gè)子節(jié)點(diǎn)到其他節(jié)點(diǎn)的距離之和。
總時(shí)間復(fù)雜度：O(n)
總空間復(fù)雜度：O(n)
go完整代碼如下：
package?main
import?"fmt"
var?N?int?=?30001
var?size?[30001]int
var?distance?[30001]int
func?sumOfDistancesInTree(n?int,?edges?[][]int)?[]int?{
????graph?:=?make([][]int,?n)
????for?i?:=?range?graph?{
????????graph[i]?=?[]int{}
????}
????for?_,?edge?:=?range?edges?{
????????u?:=?edge[0]
????????v?:=?edge[1]
????????graph[u]?=?append(graph[u],?v)
????????graph[v]?=?append(graph[v],?u)
????}
????collect(0,?-1,?graph)
????ans?:=?make([]int,?n)
????setAns(0,?-1,?0,?graph,?ans)
????return?ans
}
func?collect(cur?int,?father?int,?graph?[][]int)?{
????size[cur]?=?1
????distance[cur]?=?0
????for?_,?next?:=?range?graph[cur]?{
????????if?next?!=?father?{
????????????collect(next,?cur,?graph)
????????????distance[cur]?+=?distance[next]?+?size[next]
????????????size[cur]?+=?size[next]
????????}
????}
}
func?setAns(cur?int,?father?int,?upDistance?int,?graph?[][]int,?ans?[]int)?{
????ans[cur]?=?distance[cur]?+?upDistance
????for?_,?next?:=?range?graph[cur]?{
????????if?next?!=?father?{
????????????setAns(
????????????????next,
????????????????cur,
????????????????ans[cur]-distance[next]+size[0]-(size[next]<<1),
????????????????graph,
????????????????ans,
????????????)
????????}
????}
}
func?main()?{
????n?:=?6
????edges?:=?[][]int{{0,?1},?{0,?2},?{2,?3},?{2,?4},?{2,?5}}
????result?:=?sumOfDistancesInTree(n,?edges)
????fmt.Println(result)
}
rust完整代碼如下：
const?N:?usize?=?30001;
static?mut?SIZE:?[i32;?N]?=?[0;?N];
static?mut?DISTANCE:?[i32;?N]?=?[0;?N];
pub?fn?sum_of_distances_in_tree(n:?i32,?edges:?Vec<Vec<i32>>)?->?Vec<i32>?{
????let?mut?graph:?Vec<Vec<i32>>?=?vec![vec![];?n?as?usize];
????for?edge?in?edges?{
????????let?u?=?edge[0]?as?usize;
????????let?v?=?edge[1]?as?usize;
????????graph[u].push(v?as?i32);
????????graph[v].push(u?as?i32);
????}
????unsafe?{
????????collect(0,?-1,?&graph);
????????let?mut?ans:?Vec<i32>?=?vec![0;?n?as?usize];
????????set_ans(0,?-1,?0,?&graph,?&mut?ans);
????????ans
????}
}
unsafe?fn?collect(cur:?usize,?father:?i32,?graph:?&Vec<Vec<i32>>)?{
????SIZE[cur]?=?1;
????DISTANCE[cur]?=?0;
????for?next?in?&graph[cur]?{
????????let?next?=?*next?as?usize;
????????if?next?!=?father?as?usize?{
????????????collect(next,?cur?as?i32,?graph);
????????????DISTANCE[cur]?+=?DISTANCE[next]?+?SIZE[next];
????????????SIZE[cur]?+=?SIZE[next];
????????}
????}
}
fn?set_ans(cur:?usize,?father:?i32,?up_distance:?i32,?graph:?&Vec<Vec<i32>>,?ans:?&mut?Vec<i32>)?{
????unsafe?{
????????ans[cur]?=?DISTANCE[cur]?+?up_distance;
????????for?next?in?&graph[cur]?{
????????????let?next?=?*next?as?usize;
????????????if?next?!=?father?as?usize?{
????????????????set_ans(
????????????????????next,
????????????????????cur?as?i32,
????????????????????ans[cur]?-?DISTANCE[next]?+?SIZE[0]?-?(SIZE[next]?<<?1),
????????????????????graph,
????????????????????ans,
????????????????);
????????????}
????????}
????}
}
fn?main()?{
????let?n?=?6;
????let?edges?=?vec![vec![0,?1],?vec![0,?2],?vec![2,?3],?vec![2,?4],?vec![2,?5]];
????let?result?=?sum_of_distances_in_tree(n,?edges);
????println!("{:?}",?result);
}
c完整代碼如下：
#include?<stdio.h>
#include?<stdlib.h>
#define?N?30001
int?size[N];
int?distance[N];
void?collect(int?cur,?int?father,?int**?graph,?int?n);
void?setAns(int?cur,?int?father,?int?upDistance,?int**?graph,?int*?ans);
int*?sumOfDistancesInTree(int?n,?int?edges[][2])?{
????int**?graph?=?malloc(n?*?sizeof(*graph));
????for?(int?i?=?0;?i?<?n;?i++)?{
????????graph[i]?=?malloc((n?+?1)?*?sizeof(**graph));
????????for?(int?j?=?0;?j?<=?n;?j++)?{
????????????graph[i][j]?=?-1;
????????}
????}
????for?(int?i?=?0;?i?<?n?-?1;?i++)?{
????????int?u?=?edges[i][0];
????????int?v?=?edges[i][1];
????????if?(graph[u][0]?==?-1)?{
????????????graph[u][0]?=?0;
????????}
????????if?(graph[v][0]?==?-1)?{
????????????graph[v][0]?=?0;
????????}
????????int?j?=?0;
????????while?(graph[u][++j]?!=?-1);
????????graph[u][j]?=?v;
????????j?=?0;
????????while?(graph[v][++j]?!=?-1);
????????graph[v][j]?=?u;
????}
????collect(0,?-1,?graph,?n);
????int*?ans?=?malloc(n?*?sizeof(int));
????setAns(0,?-1,?0,?graph,?ans);
????for?(int?i?=?0;?i?<?n;?i++)?{
????????free(graph[i]);
????}
????free(graph);
????return?ans;
}
void?collect(int?cur,?int?father,?int**?graph,?int?n)?{
????size[cur]?=?1;
????distance[cur]?=?0;
????int?j?=?1;
????while?(graph[cur][j]?!=?-1)?{
????????int?next?=?graph[cur][j];
????????if?(next?!=?father)?{
????????????collect(next,?cur,?graph,?n);
????????????distance[cur]?+=?distance[next]?+?size[next];
????????????size[cur]?+=?size[next];
????????}
????????j++;
????}
}
void?setAns(int?cur,?int?father,?int?upDistance,?int**?graph,?int*?ans)?{
????ans[cur]?=?distance[cur]?+?upDistance;
????int?j?=?1;
????while?(graph[cur][j]?!=?-1)?{
????????int?next?=?graph[cur][j];
????????if?(next?!=?father)?{
????????????setAns(
????????????????next,
????????????????cur,
????????????????ans[cur]?-?distance[next]?+?size[0]?-?(size[next]?<<?1),
????????????????graph,
????????????????ans
????????????);
????????}
????????j++;
????}
}
int?main()?{
????int?n?=?6;
????int?edges[][2]?=?{?{0,?1},?{0,?2},?{2,?3},?{2,?4},?{2,?5}?};
????int*?result?=?sumOfDistancesInTree(n,?edges);
????for?(int?i?=?0;?i?<?n;?i++)?{
????????printf("%d?",?result[i]);
????}
????printf("\n");
????free(result);
????return?0;
}
c++完整代碼如下：
#include?<iostream>
#include?<vector>
//using?namespace?std;
const?int?N?=?30001;
static?int?size[N];
static?int?distance[N];
void?collect(int?cur,?int?father,?std::vector<std::vector<int>>&?graph);
void?setAns(int?cur,?int?father,?int?upDistance,?std::vector<std::vector<int>>&?graph,?int*?ans);
int*?sumOfDistancesInTree(int?n,?std::vector<std::vector<int>>&?edges)?{
????std::vector<std::vector<int>>?graph(n);
????for?(auto?edge?:?edges)?{
????????int?u?=?edge[0];
????????int?v?=?edge[1];
????????graph[u].push_back(v);
????????graph[v].push_back(u);
????}
????collect(0,?-1,?graph);
????int*?ans?=?new?int[n];
????setAns(0,?-1,?0,?graph,?ans);
????return?ans;
}
void?collect(int?cur,?int?father,?std::vector<std::vector<int>>&?graph)?{
????size[cur]?=?1;
????distance[cur]?=?0;
????for?(auto?next?:?graph[cur])?{
????????if?(next?!=?father)?{
????????????collect(next,?cur,?graph);
????????????distance[cur]?+=?distance[next]?+?size[next];
????????????size[cur]?+=?size[next];
????????}
????}
}
void?setAns(int?cur,?int?father,?int?upDistance,?std::vector<std::vector<int>>&?graph,?int*?ans)?{
????int?a?=?N;
????ans[cur]?=?distance[cur]?+?upDistance;
????for?(auto?next?:?graph[cur])?{
????????if?(next?!=?father)?{
????????????setAns(
????????????????next,
????????????????cur,
????????????????ans[cur]?-?distance[next]?+?size[0]?-?(size[next]?<<?1),
????????????????graph,
????????????????ans
????????????);
????????}
????}
}
int?main()?{
????int?n?=?6;
????std::vector<std::vector<int>>?edges?=?{?{0,?1},?{0,?2},?{2,?3},?{2,?4},?{2,?5}?};
????int*?result?=?sumOfDistancesInTree(n,?edges);
????for?(int?i?=?0;?i?<?n;?i++)?{
????????std::cout?<<?result[i]?<<?"?";
????}
????std::cout?<<?std::endl;
????delete[]?result;
????return?0;
}
福大大架構(gòu)師每日一題
java當(dāng)死，golang當(dāng)立。最新面試題，涉及golang，rust，mysql，redis，云原生，算法，分布式，網(wǎng)絡(luò)，操作系統(tǒng)。
公眾號(hào)
