LeetCode-134-加油站
加油站
题目描述:在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。解法一:穷举法
你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。
【LeetCode-134-加油站】如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1。
说明:
示例说明请见LeetCode官网。
- 如果题目有解,该答案即为唯一答案。
- 输入数组均为非空数组,且长度相同。
- 输入数组中的元素均为非负数。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
从第一个加油站开始,判断从当前加油站开始作为起点是否可以环行一周回到起点,如果可以,则返回当前加油站的位置,如果不可以则将下一个加油站作为起点判断。具体判断某一个加油站作为起点是否可以环行的过程如下:
- 如果当前油量加上当前加油站的汽油量少于当前加油站的消耗,说明无法走到下一站,跳过这种可能性;
- 如果可以走到下一站,记录当前剩余油量和已经走过的加油站的数量,然后走到下一站,继续判断;
- 知道走到最后,如果走过所有加油站,说明以当前的起始加油站作为起点是可以环行一周的,返回起始加油站的位置。
public class LeetCode_134 {
/**
* 穷举法
*
* @param gas
* @param cost
* @return
*/
public static int canCompleteCircuit(int[] gas, int[] cost) {
// 总共有n个加油站
int totalN = gas.length;
// 从第一个加油站开始遍历
for (int i = 0;
i < totalN;
i++) {
int gasCount = 0, startStation = i, runStationCount = 0;
boolean flag = true;
while (runStationCount < totalN) {
// 如果当前油量加上当前加油站的汽油量少于当前加油站的消耗,说明无法走到下一站,跳过这种可能性
if (gasCount + gas[startStation] < cost[startStation]) {
flag = false;
break;
} else {
// 剩余油量等于当前油量加上当前加油站的汽油量减去当前加油站的消耗
gasCount = gasCount + gas[startStation] - cost[startStation];
// 走过的加油站
runStationCount++;
// 下个加油站
startStation++;
if (startStation == totalN) {
// 如果下个加油站等于n,从第一个加油站开始
startStation = 0;
}
}
}
if (flag && runStationCount == totalN) {
return i;
}
}
return -1;
}public static void main(String[] args) {
int[] gas = new int[]{1, 2, 3, 4, 5};
int[] cost = new int[]{3, 4, 5, 1, 2};
System.out.println(canCompleteCircuit(gas, cost));
}
}
【每日寄语】 世上无难事,只怕有心人。一个人在实现理想的过程中,会遇到很多的困难,这不要紧,只要自己有那份心,坚持做下去,你就会成功。
推荐阅读
- “兴成长计划”我的加油站
- 2018.9.27号
- 《洋葱阅读法》day1
- 2018-10-12心力篇学习笔记(70/100)(崔律·100天精力和时间管理训练营10.5能量加油站)
- 街头小景
- 遇见#下班加油站#开启改变之路,小白多多
- 深夜加油站遇见苏格拉底-1.13
- 《洋葱阅读法》day9
- 犹太人做生意就很会做。一个十字路口,第一个人开了一个加油站,第二个人开商店,第三个人开饭馆,第四个开别的。中国人在一个路口开了一家饭店,
- 加油站监控安防系统设计方案