https://leetcode.com/problems/gas-station/
这道转圈加油问题不算很难，只要想通其中的原理就很简单。我们首先要知道能走完整个环的前提是gas的总量要大于cost的总量，这样才会有起点的存在。假设开始设置起点start = 0, 并从这里出发，如果当前的gas值大于cost值，就可以继续前进，此时到下一个站点，剩余的gas加上当前的gas再减去cost，看是否大于0，若大于0，则继续前进。当到达某一站点时，若这个值小于0了，则说明从起点到这个点中间的任何一个点都不能作为起点，则把起点设为下一个点，继续遍历。当遍历完整个环时，当前保存的起点即为所求
https://www.jianshu.com/p/ff89cae12c74
而根据上述observation，若station i无法达到station j，则station i与j之间的任何station，都无法到达station j！！！
因此，station i与j之间的任何station，都无法作为start station（因为它们连j都到不了，更别说绕足一圈了），下次搜索可以直接跳到station j！！！
参考下图：
在遍历到station i时，判断它是否能够达到后面的节点，发现i+1,i+2,i+3均可以到达，直到station j，net[j]<0因此i不能到达j。
下面重点来了，net[j]取决于从i开始net之和，由于前三个节点可以达到，对应的net都是大于0的！！！
因此，若以station i+1作为start，到station j的net[j]只会更小，所以必然小于0！！！
因此station i,i+1,i+2,i+3这三个station，都无法到达station j！！！
英文版证明：
Proof to the first point: say there is a point C between A and B -- that is A can reach C but cannot reach B. Since A cannot reach B, the gas collected between A and B is short of the cost. Starting from A, at the time when the car reaches C, it brings in gas >= 0, and the car still cannot reach B. Thus if the car just starts from C, it definitely cannot reach B.
why？我第一次看到的时候真是没啥头绪。。。
证明如下，用的类似数学归纳法，感谢discuss上的大神。。。
Proof for the second point:
https://blog.csdn.net/kenden23/article/details/14106137
这道题也挺麻烦的。乍看不难，用最简单的算法就是一个一个点地计算，计算到没油了，证明这点不能作为出发点。移动到下一个点作为出发点。这样的话思路还是挺简单的，不过这样写不accepted的，因为编译超时。
我觉得做这道题的关键是要可以总结出来这道题目的属性，注意Note这个地方，其属性主要有两个：
1 如果总的gas - cost小于零的话，那么没有解返回-1
2 如果前面所有的gas - cost加起来小于零，那么前面所有的点都不能作为出发点。
2013-12-1 update:
原创： 靖心http://write.blog.csdn.net/postedit/14106137
第一个属性的正确性很好理解。那么为什么第二个属性成立呢？
首先我们是从i =0个gas station计算起的，设开始剩油量为left=0，如果这个station的油是可以到达下一个station的，那么left=gas-cost为正数，
到了下一个station就有两种情况：
1 如果i=1个station的gas-cost也为正，那么前面的left加上当前station的剩油量也为正。
2 如果i=1个station的gas-cost为负，那么前面的left加上当前的station的剩油量也有两种情况：
一） left为正，那么可以继续到下一个station，重复前面计算i=2,i=3...，直到发生第二）种情况
二）如果left为负，那么就不能到下一个station了，这个时候如果i=k(i<k<n)，这个时候是否需要从第i=1个station开始重新计算呢？不需要，因为第k个station之前的所有left都为正的，到了第k个station才变成负。
证明：
left(i)>0, 如果left(i+1)<0，从i+1个station重新开始测试是没有必要的；如果left(i+2) > 0呢？ 那么left(i) + left(i+1)>0; left(i) + left(i+1) +left(i+2) > left(i+2)那么从i+2个station开始也是没有必要的，以此类推……left(i) + ...+ left(k-2)>0, 那么left(i)+...+left(k-2) > left(k-1)， 那么就是没有必要从第k-1个节点重新开始计算了，现在到了第k个station的剩油量left变为负，也不能作为出发点，那么直接到k+1个计算就可以了。这就可以得出属性2了。
以前没重视数学的证明定理的方法，要去证明一个定理是很困难的。但是原来证明的方法主要不是用来证明定理的，而是用来发现规则和特征的。
https://leetcode.com/problems/gas-station/discuss/42568/Share-some-of-my-ideas.
http://comproguide.blogspot.com/2014/09/gas-station-problem.html
http://yucoding.blogspot.com/2013/12/leetcode-question-gas-station.html
The idea is: consider the case that, if started at station i, and when goes to the station j, there is not enough gas to go the j+1 station. What happened now? For the brutal force method, we go back to the sataion i+1 and do the same thing. But, actually, if the accumutive gas cannot make it from j to j+1, then the stations from i to j are all not the start station. That is because, (1)the tank is unlimited, every time arrive to the station, the tank will fuel the max gas here, and comsume the cost to go to the next. (2)There can not be negative tank when arriving a station, at least the tank is empty. So, if i to j cannot go to j+1, then i+1 to j still cannot go to j+1... In this way, the next starting station we will try is not i+1, but the j+1. And after a single loop from i to j, we can find the result!
http://blog.csdn.net/kenden23/article/details/14106137
X.
我们也可以从后往前遍历，用一个变量mx来记录出现过的剩余油量的最大值，total记录当前剩余油量的值，start还是记录起点的位置。当total大于mx的时候，说明当前位置可以作为起点，更新start，并且更新mx。为啥呢？因为我们每次total加上的都是当前位置的油量减去消耗，如果这个差值大于0的话，说明当前位置可以当作起点，因为从当前位置到末尾都不会出现油量不够的情况，而一旦差值小于0的话，说明当前位置如果是起点的话，油量就不够，无法走完全程，所以我们不更新起点位置start。最后结束后我们还是看totoa是否大于等于0，如果其小于0的话，说明没有任何一个起点能走完全程，因为总油量都不够
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.https://baihuqian.github.io/2018-06-23-gas-station/
Observation 1: If car starts at A and can not reach B, then any stations between A and B can not reach B. (B is the first station that A can not reach.)
Proof by contradiction: suppose there exists a station C between A and B, that the car can reach B from C. This means the car can reach B with
tank = 0 from C. However, because the car can reach C from A, meaning tank >= 0 at station C from A. Therefore, the car can reach B from A.
Observation 2: If the total number of gas is bigger than the total number of cost. There must be a solution.
Proof: If the gas is more than the cost in total, there must be some stations we have enough gas to go through them. Let’s say they are green stations. So the other stations are red. The adjacent stations with same color can be joined together as one. Then there must be a red station that can be joined into a precedent green station unless there isn’t any red station, because the total gas is more than the total cost. In other words, all of the stations will join into a green station at last.
http://www.cnblogs.com/grandyang/p/4266812.html这道转圈加油问题不算很难，只要想通其中的原理就很简单。我们首先要知道能走完整个环的前提是gas的总量要大于cost的总量，这样才会有起点的存在。假设开始设置起点start = 0, 并从这里出发，如果当前的gas值大于cost值，就可以继续前进，此时到下一个站点，剩余的gas加上当前的gas再减去cost，看是否大于0，若大于0，则继续前进。当到达某一站点时，若这个值小于0了，则说明从起点到这个点中间的任何一个点都不能作为起点，则把起点设为下一个点，继续遍历。当遍历完整个环时，当前保存的起点即为所求
https://www.jianshu.com/p/ff89cae12c74
这是将O(n^2)复杂度变为O(N)的关键一步，原先的搜索判断每一个station是否可以成为start station。对于station[0...i...n]而言，若station i不能作为start， 则判断i+1是否可以作为start。
- If car starts at A and can not reach B. Any station between A and B
can not reach B.(B is the first station that A can not reach.)
而根据上述observation，若station i无法达到station j，则station i与j之间的任何station，都无法到达station j！！！
因此，station i与j之间的任何station，都无法作为start station（因为它们连j都到不了，更别说绕足一圈了），下次搜索可以直接跳到station j！！！
参考下图：
gas station.png
下面重点来了，net[j]取决于从i开始net之和，由于前三个节点可以达到，对应的net都是大于0的！！！
因此，若以station i+1作为start，到station j的net[j]只会更小，所以必然小于0！！！
因此station i,i+1,i+2,i+3这三个station，都无法到达station j！！！
英文版证明：
Proof to the first point: say there is a point C between A and B -- that is A can reach C but cannot reach B. Since A cannot reach B, the gas collected between A and B is short of the cost. Starting from A, at the time when the car reaches C, it brings in gas >= 0, and the car still cannot reach B. Thus if the car just starts from C, it definitely cannot reach B.
这个也非常tricky！！！遍历所有station后，只要gas的总和大于cost的总和，则必然存在一个解！！！
- If the total number of gas is bigger than the total number of cost. There must be a solution.
why？我第一次看到的时候真是没啥头绪。。。
证明如下，用的类似数学归纳法，感谢discuss上的大神。。。
Proof for the second point:
- If there is only one gas station, it’s true.
- If there are two gas stations a and b, and gas(a) cannot afford cost(a), i.e., gas(a) < cost(a), then gas(b) must be greater than cost(b), i.e., gas(b) > cost(b), since gas(a) + gas(b) > cost(a) + cost(b); so there must be a way too.
- If there are three gas stations a, b, and c, where gas(a) < cost(a), i.e., we cannot travel from a to b directly, then:
- either if gas(b) < cost(b), i.e., we cannot travel from b to c directly, then gas(c) > cost(c), so we can start at c and travel to a; since gas(b) < cost(b), gas(c) + gas(a) must be greater than cost(c) + cost(a), so we can continue traveling from a to b.
- Key Point: this can be considered as there is one station at c’ with gas(c’) = gas(c) + gas(a) and the cost from c’ to b is cost(c’) = cost(c) + cost(a), and the problem reduces to a problem with two stations. This in turn becomes the problem with two stations above.
- or if gas(b) >= cost(b), we can travel from b to c directly. Similar to the case above, this problem can reduce to a problem with two stations b’ and a, where gas(b’) = gas(b) + gas(c) and cost(b’) = cost(b) + cost(c). Since gas(a) < cost(a), gas(b’) must be greater than cost(b’), so it’s solved too.
- For problems with more stations, we can reduce them in a similar way. In fact, as seen above for the example of three stations, the problem of two stations can also reduce to the initial problem with one station.
这道题也挺麻烦的。乍看不难，用最简单的算法就是一个一个点地计算，计算到没油了，证明这点不能作为出发点。移动到下一个点作为出发点。这样的话思路还是挺简单的，不过这样写不accepted的，因为编译超时。
我觉得做这道题的关键是要可以总结出来这道题目的属性，注意Note这个地方，其属性主要有两个：
1 如果总的gas - cost小于零的话，那么没有解返回-1
2 如果前面所有的gas - cost加起来小于零，那么前面所有的点都不能作为出发点。
2013-12-1 update:
原创： 靖心http://write.blog.csdn.net/postedit/14106137
第一个属性的正确性很好理解。那么为什么第二个属性成立呢？
首先我们是从i =0个gas station计算起的，设开始剩油量为left=0，如果这个station的油是可以到达下一个station的，那么left=gas-cost为正数，
到了下一个station就有两种情况：
1 如果i=1个station的gas-cost也为正，那么前面的left加上当前station的剩油量也为正。
2 如果i=1个station的gas-cost为负，那么前面的left加上当前的station的剩油量也有两种情况：
一） left为正，那么可以继续到下一个station，重复前面计算i=2,i=3...，直到发生第二）种情况
二）如果left为负，那么就不能到下一个station了，这个时候如果i=k(i<k<n)，这个时候是否需要从第i=1个station开始重新计算呢？不需要，因为第k个station之前的所有left都为正的，到了第k个station才变成负。
证明：
left(i)>0, 如果left(i+1)<0，从i+1个station重新开始测试是没有必要的；如果left(i+2) > 0呢？ 那么left(i) + left(i+1)>0; left(i) + left(i+1) +left(i+2) > left(i+2)那么从i+2个station开始也是没有必要的，以此类推……left(i) + ...+ left(k-2)>0, 那么left(i)+...+left(k-2) > left(k-1)， 那么就是没有必要从第k-1个节点重新开始计算了，现在到了第k个station的剩油量left变为负，也不能作为出发点，那么直接到k+1个计算就可以了。这就可以得出属性2了。
以前没重视数学的证明定理的方法，要去证明一个定理是很困难的。但是原来证明的方法主要不是用来证明定理的，而是用来发现规则和特征的。
第一种代码简单，却比较难想出来，第二种还比较好想出来吧。
我想想到底如何对付这些题目呢？尤其如果面试的时候，时间又受限，那更高难度了。
我想想到底如何对付这些题目呢？尤其如果面试的时候，时间又受限，那更高难度了。
我想到的策略就是：先举些列子，观察他们的特性，然后总结出来，再设计算法吧。谁没做过，能一下子就看出其中的规律吗？
证明的时候，使用反证法会简单点。
I have thought for a long time and got two ideas:
- If car starts at A and can not reach B. Any station between A and B
can not reach B.(B is the first station that A can not reach.) - If the total number of gas is bigger than the total number of cost. There must be a solution.
http://comproguide.blogspot.com/2014/09/gas-station-problem.html
For example we start at station i and reached station j and we can not proceed tostation (j+1). In a naive approach we start from station (i+1) and see if we can reachstation (j+1). This approach works, but it takes O(n2) time.
The catch here is that we can actually start from (j+1) because of the following reason.
If we start at any index between [i+1,j] we can not reach (j+1) since at each step in the previous iteration we had zero or more gas but still we were unable to reach j+1.
http://yucoding.blogspot.com/2013/12/leetcode-question-gas-station.html
The idea is: consider the case that, if started at station i, and when goes to the station j, there is not enough gas to go the j+1 station. What happened now? For the brutal force method, we go back to the sataion i+1 and do the same thing. But, actually, if the accumutive gas cannot make it from j to j+1, then the stations from i to j are all not the start station. That is because, (1)the tank is unlimited, every time arrive to the station, the tank will fuel the max gas here, and comsume the cost to go to the next. (2)There can not be negative tank when arriving a station, at least the tank is empty. So, if i to j cannot go to j+1, then i+1 to j still cannot go to j+1... In this way, the next starting station we will try is not i+1, but the j+1. And after a single loop from i to j, we can find the result!
http://blog.csdn.net/kenden23/article/details/14106137
int canCompleteCircuit(vector<int> &gas, vector<int> &cost)
{
int sum = 0;
int total = 0;
int j = -1;
for(int i = 0; i < gas.size() ; ++i)
{
sum += gas[i]-cost[i];
total += gas[i]-cost[i];
if(sum < 0)
{
j=i; sum = 0;
}
}
if(total<0) return -1;
else return j+1;
}
[LeetCode] Gas Station, SolutionX.
我们也可以从后往前遍历，用一个变量mx来记录出现过的剩余油量的最大值，total记录当前剩余油量的值，start还是记录起点的位置。当total大于mx的时候，说明当前位置可以作为起点，更新start，并且更新mx。为啥呢？因为我们每次total加上的都是当前位置的油量减去消耗，如果这个差值大于0的话，说明当前位置可以当作起点，因为从当前位置到末尾都不会出现油量不够的情况，而一旦差值小于0的话，说明当前位置如果是起点的话，油量就不够，无法走完全程，所以我们不更新起点位置start。最后结束后我们还是看totoa是否大于等于0，如果其小于0的话，说明没有任何一个起点能走完全程，因为总油量都不够
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int total = 0, mx = -1, start = 0; for (int i = gas.size() - 1; i >= 0; --i) { total += gas[i] - cost[i]; if (total > mx) { start = i; mx = total; } } return (total < 0) ? -1 : start; }
X. Brute Force
开始的思路是用深度搜索的方法，尝试从每个加油站走，看是否能走完一圈。
public int canCompleteCircuit(int[] gas, int[] cost) {
if (gas == null || gas.length < 2) {
return 0;
}
int len = gas.length;
int[] circle = new int[2*len];
for (int i = 0; i < circle.length; i++) {
circle[i] = gas[i % len];
}
for (int i = 0; i < len; i++) {
if (helper(circle, cost, 0, 0, 0)) {
return i;
}
}
return -1;
}
private boolean helper(int[] circle, int[] cost, int pos, int num, int gas) {
if (num == cost.length) {
return true;
}
gas += circle[pos] - cost[pos % cost.length];
if (gas < 0) {
return false;
}
return helper(circle, cost, pos + 1, num + 1, gas);
}
