134. Gas Station
Question
You are given two arrays, one with the amount of gas that can be filled at each gas station, and the other with the amount of gas consumed from the current gas station to the next gas station. Ask if there exists a gas station from which you can go until you return to it again. Existence returns the index of that gas station, and non-existence returns -1.
Example:
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 units 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.
The cost is 5.
## Algorithm
This problem is relatively simple to implement according to the question. We use the violent method to simulate the advance from each gas station, each time we reach a gas station, refuel, and then see if we can reach the next gas station (we use left here to represent the amount of gas left to the next gas station), a negative amount of gas left means we can't reach it, a non-negative amount means we can.
Code 1 is an implementation of this idea. However, the time complexity will time out.
If you look at the answer, it introduces an algorithmic idea that relies on some mathematical proof.
If the sum of an array is non-negative, then it must be possible to find a starting position from which the sum is always non-negative when circling the array.
(The proof does not seem to be difficult, there will be time to add later)
With this theorem, it is very easy to determine whether there is such a solution, just need to calculate the total fuel consumption to see if it is greater than or equal to 0.
Notice the phenomenon that
1. if you start from position i, i + 1, i + 2 ... If you drive all the way over, the gas tank is not empty. What does that mean? It means that from i to i+1, i+2, ... It must be a positive accumulation. 2.
2. now suddenly find that the tank is empty when driving to position j. What does this mean? It means that we can't go all the way from position i. 3.
3. Because we already know that position i is definitely positive accumulation, so if we start from position i+1, it is equivalent to one less chance to refuel, so there is even less fuel and we can't go the whole way. Similarly, there is no need to start from i+2, i+3, ... and so on. So we can safely start from position j+1.
Write code 2 along these lines.
## Code 1
```java
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
for (int i = 0; i < gas.length; i++) {
int left = 0.
for (int j = 0; j < gas.length; j++) {
left = left + gas[(i + j) % gas.length] - cost[(i + j) % gas.length].
if (left < 0) break.
}
if (left >= 0) {
return i.
}
}
return -1.
}
}
Time Complexity: O(n*n)
Submit because the TLE will not pass.
Code 2
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int sum = 0.
int total = 0.
int start = 0.
for (int i = 0; i < gas.length; i++) {
int diff = gas[i] - cost[i].
sum += diff.
total += diff.
if (sum < 0) {
start = i + 1.
sum = 0.
}
}
return total >= 0 ? start : -1.
}
}
题目
给你两个数组，一个是每个加油站可以加多少油，另一个是当前加油站到下一个加油站的消耗的汽油。问是否存在从某一个加油站出发，可以一直走直到再次回到这个加油站。存在返回那个加油站的index，不存在返回-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.
算法
这个题目，按照题意来说是比较简单的实现。用暴力法从每个加油站开始模拟前进，每次到加油站后加油，然后再看是否能到下一个加油站（我们这里使用left代表到下一个加油站剩余的油量），剩余油量为负数则说明到不了，为非负数则说明可以到。
代码1就是执行了这个思路。然而时间复杂度会超时。
看答案的话介绍的是一个依靠某个数学证明的算法思路。
如果一个数组的总和非负，那么一定可以找到一个起始位置，从他开始绕数组一圈，累加和一直都是非负的
（证明貌似不难，以后有时间再补）
有了这个定理，判断到底是否存在这样的解非常容易，只需要把全部的油耗情况计算出来看看是否大于等于0即可。
注意到这样一个现象：
- 假如从位置i开始，i+1，i+2...，一路开过来一路油箱都没有空。说明什么？说明从i到i+1，i+2，...肯定是正积累。
- 现在突然发现开往位置j时油箱空了。这说明什么？说明从位置i开始没法走完全程。
- 因为前面已经知道，位置i肯定是正积累，那么，如果从位置i+1开始相当于减少了一个加油的机会，油更少了，更加没法走完全程了。同理，也不用从i+2，i+3，...开始尝试。所以我们可以放心地从位置j+1开始尝试。
写出代码2依照这个思路。
代码1
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
for (int i = 0; i < gas.length; i++) {
int left = 0;
for (int j = 0; j < gas.length; j++) {
left = left + gas[(i + j) % gas.length] - cost[(i + j) % gas.length];
if (left < 0) break;
}
if (left >= 0) {
return i;
}
}
return -1;
}
}
时间复杂度: O(n*n)
提交因为TLE不会通过。
代码2
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int sum = 0;
int total = 0;
int start = 0;
for (int i = 0; i < gas.length; i++) {
int diff = gas[i] - cost[i];
sum += diff;
total += diff;
if (sum < 0) {
start = i + 1;
sum = 0;
}
}
return total >= 0 ? start : -1;
}
}