LeetCode OJ--Gas Station**
https://oj.leetcode.com/problems/gas-station/
啊，好笨，刚开始一直超时，复杂度为n*n。
class Solution { public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { bool may_able = false; for(unsigned int i = 0;i<gas.size();i++) { if(gas[i]>=cost[i]) may_able = true; } if(may_able == false) return -1; double amount = 0; //轮流做start for(unsigned int start = 0;start<gas.size();start++) { amount = gas[start] - cost[start]; if(amount < 0) continue; bool flag = true; //对每个轮流进行检查 for(unsigned next = (start + 1)%gas.size(); next%gas.size()!=start; next = (next%gas.size()) + 1) { amount += gas[next] - cost[next]; if(amount<0) { flag = false; break; } } if(flag == true) return start; } return -1; } };
之后，看了别人的答案。但是在实现的时候还是超时，发现是出现了死循环。
如果从start开始，往后累加了几步出现了负数，则中间的这几个点，肯定也不能作为start,因为中间的步累加的结果都是正的，如果去掉了原来的start，和肯定是更小的。
class Solution { public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { double amount = 0; //轮流做start for(unsigned int start = 0;start<gas.size();start++) { amount = gas[start] - cost[start]; if(amount < 0) continue; //对每个轮流进行检查 for(unsigned next = (start + 1)%gas.size(); ; next = (next+1)%gas.size()) { amount += gas[next] - cost[next]; if(amount<0) { start = ((next + 1)%gas.size()) - 1; break; } if(next==start) return start; } } return -1; } };
于是，在男友的修改下：今天脑袋彻底不好使了。
class Solution { public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { double amount = 0; //轮流做start for(unsigned int start = 0;start<gas.size();start++) { amount = gas[start] - cost[start]; if(amount < 0) continue; //对每个轮流进行检查 for(unsigned next = (start + 1)%gas.size(); ; next = (next+1)%gas.size()) { amount += gas[next] - cost[next]; if(amount<0) { if(next > start) start = next; else return -1; //后面的点作为中间点，是已经循环过的了！！！！ break; } if(next==start) return start; } } return -1; } };
笨死了