class Solution { public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { int len = gas.size(); if (len < 1 || len != cost.size()) return -1; vector<int> diff(len, 0); for (int i=0; i<len; i++) { diff[i] = gas[i] - cost[i]; } int p = len - 1; int q = 0; int sum = diff.back(); int walk= len - 1; while (walk > 0) { while (walk > 0 && sum + diff[q] >= 0) { sum += diff[q++]; walk--; } while (walk > 0 && sum + diff[q] < 0) { sum += diff[--p]; walk--; } } if (sum < 0) return -1; return p == q ? p : -1; } };
这题直接穷举的话就是O(N^2),估计会超时吧,于是想其他办法几度想去搜答案了,还是蒙了一下,思路:
先求出每个加油站和下一段路所需燃油的差存到diff中,这样问题就转换为,从diff的哪个元素开始向右绕一圈,每一步的diff前缀和始终为非负值,
因为要绕一圈必然包含所有的元素,那么先从diff的最后一个元素开始,如果是一个负值(gas[i]-cost[i] < 0)说明从该加油站直接开始是不行的,前面必定有加油站加油后多了一些出来才能补上这个负值,那我们就一直向前遍历diff元素,直到他们的和能填补这个负值为止,这时候的索引就是目前暂定的开始索引(开始为什么选择从最后一个元素进行,因为绕一圈起点最极端的情况就是从最后一个元素开始,然后一个个向前排除),有了前面的这些diff遍历后,一般他们的和会是个正数也就是说有油多出来,这时候我们尝试向diff后面的元素遍历(因为一开始在最后一个节点,这里的向后遍历,其实是从diff下标0开始向后遍历了),直到油不够。再向前遍历企图找到使得累加和为正的diff元素索引,这样的一个过程反复进行最后就可以得到结果了。
当然这题里假设如果有解的话只有一个,否则会有问题吧
另外看了下zheli哥的题解,有证明感觉比瞎蒙好
http://www.cnblogs.com/zhuli19901106/p/3568203.html
LeetCode Gas Station,布布扣,bubuko.com
原文:http://www.cnblogs.com/lailailai/p/3728690.html