贪心1
时间复杂度 O(n) 空间复杂度O(1)
情况一:如果gas的总和小于cost总和,那么无论从哪里出发,一定是跑不了一圈的
情况二:gas[i] = gas[i]-cost[i]为一天剩下的油,i从0开始计算累加到最后一站,如果累加没有出现负数,说明从0出发,油就没有断过,那么0就是起点。
情况三:如果累加的最小值是负数,汽车就要从非0节点出发,从后向前,看哪个节点能把这个负数填平,能把这个负数填平的节点就是出发节点。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
for(int i = 0; i < gas.size(); i++) gas[i] -= cost[i];
int m = INT_MAX, add = 0;
for(int i = 0; i < gas.size(); i++) {
add += gas[i];
m = min(m, add);
}
if(add >= 0) {
if(m >= 0) return 0;
int i;
for(i = gas.size() - 1; i >= 0; i--) {
m += gas[i];
if(m >= 0) return i;
}
}
return -1;
}
};
贪心2
时间复杂度 O(n) 空间复杂度O(1)
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int rest_end = 0, add = 0, start = 0;
//add为从start开始累加
//rest_end为从0累加
for(int i = 0; i < gas.size(); i++) {
add += gas[i] - cost[i];
rest_end += gas[i] - cost[i];
if(add < 0) {//当前累加一旦小于0
start = i+1;//更新起始位置
add = 0;//当前累加清0
}
}
if(rest_end >= 0) return start;
else return -1;
}
};