这一题是贪心不是模拟 是贪心不是模拟 是贪心不是模拟!
如果用模拟的做法会比较慢,也失去了做这一题的趣味了。
模拟的方法很简单,就是每一个加油站都做起点模拟一遍,试一下能不能完成一圈,能完成一圈就保存答案,不能完成的就往下一个找
如果都不能完成则返回-1
贪心的做法非常的巧妙,整个循环数组如下性质。
对于一个循环数组,如果这个数组整体和 >= 0,那么必然可以在数组中找到这么一个元素:从这个数组元素出发,绕数组一圈,能保证累加和一直是出于非负状态。
这个需要用集合的方法证明:
循环数组分成两个必存在一个区间二分,使得{区间1的和}>0 且{区间1的和}>=abs{区间2的和}。
我们只要从这个找到的区间1的起始位置出发,必然能累加和处于非负状态。
注释中有讲解如何处理一些细节的问题。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n=gas.size();
int j=-;
int sum=,total=;
for(int i=;i<n;i++){
sum+=gas[i]-cost[i];
total+=gas[i]-cost[i];
if(sum<){
/*说明之前的油不能支撑到这个加油站,之前的加油站都不能作为起点*/
sum=;
/*重置为0*/
j=i;
/*将此加油站后一点设为起点再寻找*/
}
}
/*先判断total是否小于0,小于0说明找不到这个起始点*/
if(total<)return -;
else return j+;
}
};