0%

LeetCode: Gas Station

贪心

遍历两次,第一次找到一个起点idx,它到达最后一个加油站,加了油,再到第一个加油站的时候,油箱油量不是负数的。

然后我们就判断,从第一个加油站到idx,能否到达。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int size=gas.size();
vector<int> remain(size,0);
for(int i=0;i<size;++i)
remain[i]=gas[i]-cost[i];

int current=0;
int idx=0;
for(int i=0;i<size;++i)
{
current+=remain[i];
if(current<0)
{
current=0;
idx=i+1;
}
}

if(idx==size)
return -1;
if(idx==0)
return idx;
for(int i=0;i<idx;++i)
{
current+=remain[i];
if(current<0)
return -1;
}
return idx;
}
};