每天一道LeetCode-----存在一个由加油站组成的环路，判断是否可以从某个加油站出发环绕一周

Gas Station

原题链接Gas Station

加油站问题，判断是否能够从一个加油站开始行走环绕一周，其中gas[i]表示在第i个加油站可以获得的油量，cost[i]表示从第i个加油站到达第i+1个加油站所需的油量

如果gas[i] >= cost[i]，那么可以说在加油站i处是盈利的

那么可以从每个盈利的加油站出发，判断是否可以环绕一周，当然这里有个小技巧，就是如果假设i, i+1, i+2, …, j这几个连续加油站都是盈利的，那么就只需要从i出发就可以，无需判断从i+1,i+2,…,j这几个加油站出发的情况

代码如下

class Solution { public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {if(gas.empty()) return -1;int n = gas.size();int start = 0;while(start < n){if(gas[start] >= cost[start]){if(run(gas, cost, start))return start;while(start + 1 < n && gas[start + 1] >= cost[start + 1])++start;}++start;}return -1;} private:bool run(vector<int>& gas, vector<int>& cost, int start){int curPos = start;int curGas = gas[start];int n = gas.size();while(true){curGas -= cost[curPos];if(curGas < 0)return false;curPos = (curPos + 1) % n;if(curPos == start)return true;curGas += gas[curPos];}} };

总结

以上是生活随笔为你收集整理的每天一道LeetCode-----存在一个由加油站组成的环路，判断是否可以从某个加油站出发环绕一周的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。