[LeetCode]134. Gas Station

Problem

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

If there exists a solution, it is guaranteed to be unique. Both input arrays are non-empty and have the same length. Each element in the input arrays is a non-negative integer. Example 1:

Input: gas = [1,2,3,4,5] cost = [3,4,5,1,2]

Output: 3

Explanation: Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 4. Your tank = 4 - 1 + 5 = 8 Travel to station 0. Your tank = 8 - 2 + 1 = 7 Travel to station 1. Your tank = 7 - 3 + 2 = 6 Travel to station 2. Your tank = 6 - 4 + 3 = 5 Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3. Therefore, return 3 as the starting index. Example 2:

Input: gas = [2,3,4] cost = [3,4,3]

Output: -1

Explanation: You can’t start at station 0 or 1, as there is not enough gas to travel to the next station. Let’s start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 0. Your tank = 4 - 3 + 2 = 3 Travel to station 1. Your tank = 3 - 3 + 3 = 3 You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3. Therefore, you can’t travel around the circuit once no matter where you start.

Solution

解析

给定两个数组,一个数组表明n个点,每个点汽油的存储量,另一个数组表明从当前点到下一个点的耗油量。计算从一个点能否转一圈,返回到这个点?如果能,返回这个点的编号;如果不能返回-1。

首先,可以知道,如果所有点的汽油存储量小于耗油量,一定不能转一圈。其他情况,一定存在一个解,现在就是要找到这个解。

最原始的解法是:遍历n个点,以每个点作为起点,遍历一圈,计算当前点汽油的剩余量,如果小于0,换下一个起点,否则,返回这个起点。

Code

Naive Version

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
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int size = gas.size();
vector<int> remain(size, 0);
int sum = 0;
for (int i=0; i< size; ++i){
remain[i] = gas[i] - cost[i];
sum += remain[i];
}
if (sum < 0) return -1;

for (int i=0; i < size; ++i)
{
if (remain[i] < 0) continue;
int j = i, temp = 0;
while (((j + 1)%size != i) && (temp += remain[j]) >= 0)
{
j = (j + 1) % size;
}
if (temp < 0) continue;
if (i == 0) j = size - 1;
else j = i - 1;
temp += remain[j];
if (temp >= 0)
return i;
}
return -1;
}
};

Improved Version 上面版本,反复计算次数过多,导致效率降低。通过观察,发现,如果点A到B,汽油剩余量小于0,那么,A-B这些点都能作为起点,比如说测试用例1,第一个点,为-2,当前点0,不能作为起点,从下一个点开始计算,同时做一次遍历即可,找到答案。要有一个变量存储最终的汽油剩余量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int total = 0, sum = 0, start = 0;
for (int i=0; i< gas.size(); i++){//一次遍历
total += gas[i] - cost[i];
sum += gas[i] - cost[i];
if (sum < 0){//说明start和i之间的元素都不能作为起点;
start = i + 1;
sum = 0;
}
}
return total < 0 ? -1 : start;
}
};
您的支持就是我更新的最大动力!谢谢!