134. Gas Station （数学）

https://leetcode.com/problems/gas-station/description/

题目：有N个加油站点构成一个环状，每个站点i加油量为gas[i]，从站点i到站点i+1需要耗费有两为cost[i]，现要求从哪个站点出发可以成功转一圈回到初始站点，返回该站点，若没有则返回-1；

思路：
这个题要用反证法来理解。算法：
从i开始，j是当前station的指针，sum += gas[j] – cost[j] （从j站加了油，再算上从i开始走到j剩的油，走到j+1站还能剩下多少油）
如果sum < 0，说明从i开始是不行的。那能不能从i..j中间的某个位置开始呢？假设能从k (i <=k<=j)走，那么i..j < 0，若k..j >=0，说明i..k – 1更是<0，那从k处就早该断开了，根本轮不到j。
所以一旦sum<0，i就赋成j + 1，sum归零。
最后total表示能不能走一圈。
这个题算法简单，写起来真是够呛。对数组一快一慢双指针的理解还是不行。注意千万不能出现while (i < 0) { i++, A[i]}这种先++然后取值的情况，必须越界。

class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int sum=0,total=0,len=gas.size(),idex=-1;
for(int x=0;x<len;x++)
{
sum+=gas[x]-cost[x];
total+=gas[x]-cost[x];
if(sum<0) sum=0,idex=x;
}
return total>=0?idex+1:-1;
}
};

最后

以上就是缥缈睫毛膏为你收集整理的134. Gas Station （数学）的全部内容，希望文章能够帮你解决134. Gas Station （数学）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。