本文主要是介绍力扣每日一题:2477. 到达首都的最少油耗(2023-12-05),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
力扣每日一题
题目:2477. 到达首都的最少油耗
日期:2023-12-05
用时:34 m 15 s
时间:37ms
内存:84.8MB
思路:分别计算每条路上通过的城市数量(数量/座位数,向上取整),然后求和,这里每条路上通过的城市数量实际就是图中每个节点的子节点数量。
代码:
class Solution {public long minimumFuelCost(int[][] roads, int seats) {int size = roads.length+1;List<Integer>[] list = new ArrayList[size];for(int i=0;i<size;i++){list[i] = new ArrayList<>();}for(int[] road:roads){int num1 = road[0];int num2 = road[1];list[num1].add(num2);list[num2].add(num1);};dfs(0,-1,list,seats);return sum;}long sum = 0;private int dfs(int start,int end,List<Integer>[] list,int seats){int cnt =1;for(int num: list[start]){if(num!=end){cnt+=dfs(num,start,list,seats);}}if(start>0){sum+=(cnt-1)/seats+1;}return cnt;}
}
这篇关于力扣每日一题:2477. 到达首都的最少油耗(2023-12-05)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!