本文主要是介绍**Leetcode 134. Gas Station，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://leetcode.com/problems/gas-station/description/
两个结论还是很容易猜到的:
(1) sum(gas[i] - cost[i]) >=0的时候才能跑完
(2)假设最小的sum(gas[i] - cost[i])位置是k，那么应该把k+1作为起点
（3）我不是从（2）的角度考虑的 我是从最大子段和的角度考虑，具有最大子段和的位置应该作为起点。然后看是不是每个位置都能保证到达。
关于（1）（2）的证明：https://leetcode.com/problems/gas-station/discuss/42572/Proof-of-%22if-total-gas-is-greater-than-total-cost-there-is-a-solution%22.-C++
写的挺好的
We prove the following statement.
If sum of all gas[i]-cost[i] is greater than or equal to 0, then there is a start position you can travel the whole circle.
Let i be the index such that the the partial sum
gas[0]-cost[0]+gas[1]-cost[1]+...+gas[i]-cost[i]
is the smallest, then the start position should be start=i+1 ( start=0 if i=n-1). Consider any other partial sum, for example,
gas[0]-cost[0]+gas[1]-cost[1]+...+gas[i]-cost[i]+gas[i+1]-cost[i+1]
Since gas[0]-cost[0]+gas[1]-cost[1]+...+gas[i]-cost[i] is the smallest, we must have
gas[i+1]-cost[i+1]>=0
in order for gas[0]-cost[0]+gas[1]-cost[1]+...+gas[i]-cost[i]+gas[i+1]-cost[i+1] to be greater.
The same reasoning gives that
gas[i+1]-cost[i+1]>=0gas[i+1]-cost[i+1]+gas[i+2]-cost[i+2]>=0.......gas[i+1]-cost[i+1]+gas[i+2]-cost[i+2]+...+gas[n-1]-cost[n-1]>=0
What about for the partial sums that wraps around?
gas[0]-cost[0]+gas[1]-cost[1]+...+gas[j]-cost[j] + gas[i+1]-cost[i+1]+...+gas[n-1]-cost[n-1]
>=
gas[0]-cost[0]+gas[1]-cost[1]+...+gas[i]-cost[i] + gas[i+1]-cost[i+1]+...+gas[n-1]-cost[n-1]
>=0
The last inequality is due to the assumption that the entire sum of gas[k]-cost[k] is greater than or equal to 0.
So we have that all the partial sums
gas[i+1]-cost[i+1]>=0,
gas[i+1]-cost[i+1]+gas[i+2]-cost[i+2]>=0,
gas[i+1]-cost[i+1]+gas[i+2]-cost[i+2]+...+gas[n-1]-cost[n-1]>=0,
...
gas[i+1]-cost[i+1]+...+gas[n-1]-cost[n-1] + gas[0]-cost[0]+gas[1]-cost[1]+...+gas[j]-cost[j]>=0,
...
Thus i+1 is the position to start. Coding using this reasoning is as follows:
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();int total(0), subsum(INT_MAX), start(0);for(int i = 0; i < n; ++i){total += gas[i] - cost[i];if(total < subsum) {subsum = total;start = i + 1;}}return (total < 0) ? -1 : (start%n); }
};我的AC代码：
class Solution {
public:int get_idx(int pos, int n) {return (pos + n) % n;}int get_st_pos(vector<int>& gas, vector<int>& cost) {int min_v = gas[0] - cost[0], min_idx = 0;for (int i = 1; i < gas.size(); i++) {int tmp = gas[i] - cost[i];if (tmp < min_v) {min_v = tmp;min_idx = i;}}int st = get_idx(min_idx+1, gas.size());int ans = gas[st] - cost[st], sum_st = st, sum_en = st, sum = gas[st] - cost[st];int last_st = st, idx = st;for (int i = st; i < st + gas.size(); i++) {idx = get_idx(i, gas.size());if (sum < 0) {sum = gas[idx] - cost[idx];last_st = idx;} if (sum > ans) {sum_st = last_st;sum_en = idx;ans = sum;}}return sum_st;}int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {if (gas.size() <= 1) return gas[0] >= cost[0] ? 0 : -1;int st = get_st_pos(gas, cost), idx = 0, max_pos = 0, max_v = 0;int dp[gas.size() + 1];for (int i = st; i <= st + gas.size(); i++) {idx = get_idx(i, gas.size());if ( i == st ) {dp[i] = gas[i];continue;}if ( i == st + gas.size() ) {dp[idx] = dp[get_idx(i-1, gas.size())] - cost[ get_idx(i-1, gas.size()) ];if (dp[idx] < 0) return -1;continue;}dp[idx] = dp[get_idx(i-1, gas.size())] - cost[ get_idx(i-1, gas.size()) ] ;if (dp[idx] < 0) return -1;dp[idx] += + gas[ idx ];}return st;}
};这篇关于**Leetcode 134. Gas Station的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
