兰州网站开发价格,建设和住房保障部 网站,大学《网站开发与应用》试题,百度怎样收录网站题目#xff1a;
在一条环路上有 n 个加油站#xff0c;其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车#xff0c;从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发#xff0c;开始时油箱为空。
给定两个整数…题目
在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。
给定两个整数数组 gas 和 cost 如果你可以按顺序绕环路行驶一周则返回出发时加油站的编号否则返回 -1 。如果存在解则 保证 它是 唯一 的。
思路从x出发到y走不下去了。那么对于x到y中的所有节点z如果从z出发一定会在y处卡住。应用这个结论我们在遍历的时候不需要遍历x到y中的节点了只需要从走不下去的节点y的下一个节点作为起始遍历即可。
代码
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int n gas.length;// 起点iint i 0;while (i n) {int sumOfGas 0, sumOfCost 0;// 记录经过的车站数int count 0;while (count n) {int j (i count) % n;sumOfGas gas[j];sumOfCost cost[j];// 走不下去if (sumOfCost sumOfGas) {break;}count;}if (count n) return i;else i i count 1;}return -1;}
}
性能时间复杂度On 空间复杂度O1
