- Leetcode 2477. 到达首都的最少油耗(建图 + DFS 一次遍历)
- 题目
- 给你一棵 n 个节点的树(一个无向、连通、无环图),每个节点表示一个城市,编号从 0 到 n - 1 ,且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads ,其中 roads[i] = [ai, bi] ,表示城市 ai 和 bi 之间有一条 双向路 。
- 每个城市里有一个代表,他们都要去首都参加一个会议。
- 每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。
- 城市里的代表可以选择乘坐所在城市的车,或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。
- 请你返回到达首都最少需要多少升汽油。
- 1 <= n <= 10 ^ 5
- roads.length == n - 1
- roads[i].length == 2
- 0 <= ai, bi < n
- ai != bi
- roads 表示一棵合法的树。
- 1 <= seats <= 10 ^ 5
- 解法
- 建图 + DFS 一次遍历:
- 第 1 步:
- 思考不走回头路肯定是最优的,因此每个叶子节点均会发车
- 第 2 步:
- 如果车上座位比较多,则发车到父节点后,将所有人塞入最少的车
- 第 3 步:
- 实现仅在回溯时处理,
- 叶子节点发一辆车,载一个人
- 非叶子节点、将所有孩子节点的人加自己塞入最少的车
- 根节点不能再发车了
- 第 4 步:
- 具体实现可以仅回溯人数 human,使用(human+seats-1)/seats 确定最少发了几辆车
- 注意:发车到根节点即可,根节点不发车
- 时间复杂度:O(n),空间复杂度:O(n+height)建树+递归栈深度
- 代码
private long res;
public long minimumFuelCost(int[][] roads, int seats) {
this.res = 0L;
int n = roads.length + 1;
List<Integer>[] edgeList = buildTree(n, roads);
dfsTraversalTree(0, -1, edgeList, seats);
return this.res;
}
private List<Integer>[] buildTree(int n, int[][] edges) {
List<Integer>[] edgeList = new ArrayList[n];
for (int i = 0; i < n; i++) {
edgeList[i] = new ArrayList<>();
}
for (int i = 0; i < edges.length; i++) {
int u = edges[i][0];
int v = edges[i][1];
edgeList[u].add(v);
edgeList[v].add(u);
}
return edgeList;
}
private int dfsTraversalTree(int son, int father, List<Integer>[] edgeList, int seats) {
int human = 1;
if (edgeList[son].size() == 1 && edgeList[son].get(0).equals(father)) {
this.res++;
return human;
}
for (int next : edgeList[son]) {
if (next != father) {
human += dfsTraversalTree(next, son, edgeList, seats);
}
}
if (son != 0) {
this.res += (human + seats - 1) / seats;
}
return human;
}