时代和环境变化非常快速,因此我们必须持续将目光聚焦在未来。

题目描述:

加油站

在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。

给定两个整数数组 gascost ,如果你可以按顺序绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1 。如果存在解,则 保证 它是 唯一 的。

解题代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int now = 0;
int sum = 0;
int start = 0;

for(int i = 0; i < gas.size(); i++) {
now += gas[i] - cost[i];
sum += gas[i] - cost[i];
if(now < 0) {
start = i+1;
now = 0;
}
}
if(sum < 0) return -1;
return start;
}
};

总结与收获:

此题首先确立两步,一是总油量减总消耗如果大于0,那必定有解;二是遍历所有加油站,只要当前的消耗大于油量,则说明这个出发点不行,直接定义下一个加油站为起点。这样遍历一遍加油站后,就能得出有没有解。(怎么确保这是唯一解?)