首页 > 代码库 > leetcode Gas Station
leetcode Gas Station
gas[i]表示第i个站点可以加的油，cost[i]表示到下一个站点要消耗的油，一开始油箱空，假设油箱可以装无限的油。然后在一个环中。那个起点开始可以绕一圈回到原点，有且仅有一个答案。如果没有则返回-1.
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, otherwise return -1.
思路一，一开始很简单的想到就是遍历一下每个节点看看能不能走一圈就行。然后需要的剪枝是，如果该起点的cost比gas大，那就不用试了，肯定不行，还有就是如果gas-cost的累加和小于0了也是不要再继续试了。
class Solution {public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { vector<int> left(gas); for (int i = 0; i < left.size(); ++i) left[i] = cost[i] - gas[i]; for (int i = 0; i < left.size(); ++i) { int sum = 0, cnt = 0; if (left[i] > 0) for (int j = i; cnt < left.size(); ++j) { j = j % left.size(); sum += left[j]; if (sum < 0) break; } if (cnt == left.size()) return i; cnt = 0; } return -1; }};
每个节点都考虑必然超时啊。然后我们稍微改进一下就行了。
我们用left数组存每个节点剩余的油，也就是gas[i]-cost[i]，可能是负数，那么我们从0开始，如果left[i]的累加一直都大于等于0循环回到原点，那就是有解。如果累加到某个小标小于0了，那么我们不是从i+1继续判断累加值，而是从累加到的那个点的下一个点开始继续判断，因为之前的累加和已经不可能走完了，所有起点不会再前面。这样的话，我们要判断的是，一旦有绕过最后一个点又从头开始的时候，那么要么就找到了节点，要么就是没有符合的点，也就是终止条件之一了。例如我们的left数组为：
-2， 2， -2， -1， 4， 6，
然后6又循环到-2.
那么我们一开始sum是-2，那么i+1判断2大于等于0，符合，然后2+ -2 等于0还是符合，然后-1不符合了，然后4符合，4+6=10符合，然后绕到-2，变成8还是大于等于零继续，加2变10，然后-2， -1 最后回到4的时候是大于零的。所以我们刚才从4开始就是符合回来的，那么4的下标就是要返回的答案。当然我的例子举得不是很对，因为不止一个答案，6开始也可以。但题目说只有一个答案的思路和上面说的是一样的。这样就只是O(n)的时间了。
这是一开始试着写的比较挫的代码：
class Solution {public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { vector<int> left(gas); for (int i = 0; i < left.size(); ++i) left[i] = gas[i] - cost[i]; for (int i = 0; i < left.size(); ) { int sum = 0, cnt = -1, in = i; bool flag = false; while(sum >= 0) { sum += left[in]; in++; if (in >= left.size()) flag = true; in = in % left.size(); cnt++; if (cnt == left.size()) return i; } if (flag) return -1; i = in; } //return -1; }};
然后改的比较好看一点，变量少了一些如下：
class Solution {public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { vector<int> left(gas); for (int i = 0; i < left.size(); ++i) left[i] = cost[i] - gas[i]; for (int i = 0; i < left.size(); ++i) { int sum = 0, cnt = 0; if (left[i] > 0) for (int j = i; cnt < left.size(); ++j) { j = j % left.size(); sum += left[j]; if (sum < 0) break; } if (cnt == left.size()) return i; cnt = 0; } return -1; }};
leetcode Gas Station