加油站
先找可能存在开始点，再验证（超时）
先找到所有加油比消耗大的站点，是可能的开始点
然后依次验证上述点，发现油箱是负数的该点无效。发现科研走到开始点前一个并能到下一个的成功
class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int volume = 0; vector<int> start; for(int i=0 ; i<gas.size() ;i++) { if(gas[i] >= cost[i]) start.push_back(i); //找到可能开始的点 } for(int i=0 ; i < start.size() ;i++) { int result = start[i]; // cout<<"result:"<<result<<endl; for(int j = result ; j <= gas.size(); j++) //验证点是否正确 { if(j == gas.size()) j = 0; //循环数组 volume += gas[j]; volume -= cost[j]; // cout<<j<<' '<<volume<<endl; if(volume < 0 ) //检查油箱 { volume=0; break; } if((result == 0 && j== gas.size()-1 && volume >= 0) ||(result!=0 && j == result-1 && volume >= 0 ) ) //验证点成功 return result; } } return -1; } };
贪心算法
class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int curSum = 0; int totalSum = 0; int start = 0; for (int i = 0; i < gas.size(); i++) { curSum += gas[i] - cost[i]; //当前油箱 totalSum += gas[i] - cost[i];//全局油箱 if (curSum < 0) { // 当前累加rest[i]和 curSum一旦小于0 start = i + 1; // 起始位置更新为i+1 curSum = 0; // curSum从0开始 } } if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了 return start; } };
二刷
class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int gaxBox = 0 , sumBox =0; int result = 0; for(int i=0 ; i<gas.size() ;i++) { sumBox = sumBox + gas[i] - cost[i]; gaxBox = gaxBox + gas[i] - cost[i]; if(gaxBox < 0) { result = i+1; gaxBox = 0; } } if(sumBox < 0) return -1; else return result; } };
