首页 > 代码库 > Gas Station
Gas Station
题意很清晰，每个加油站有一定的油，到下一个站需要消耗一定的油量，这个关系是固定的，这样我们就可以用一个数组来表示汽车到每个加油站以及接下来一段路程增加的油量，即gas[i]-cost[i]；
例如：gas 5 0 9 4 3
cost 6 7 5 9 5
seq -1 -7 4 -5 -2
这就变成了一个最大连续子序列和的拓展问题，算法说明见链接http://blog.csdn.net/hcbbt/article/details/10454947
1 class Solution { 2 public: 3 int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { 4 int gasLen = gas.size(); 5 int sum = -1; 6 int index =-1; 7 bool round = false; 8 int cnt =0; 9 if(gasLen == 0)10 return -1;11 for(int i=0;i<gasLen;i++)12 {13 gas[i] = gas[i]-cost[i];14 }15 for(int i=0;i<2*gasLen-1;i++)16 {17 if(sum<0)18 {19 if(i>=gasLen)20 break;21 sum = gas[i];22 index = i;23 cnt = 1;24 }25 else26 {27 sum += gas[i%gasLen];28 cnt++;29 }30 if(sum>=0&&cnt == gasLen)31 break;32 33 }34 if(sum<0)35 return -1;36 return index;37 }38 };
Gas Station
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。