一.相关链接
题目链接:134. 加油站
二.心得体会
这道题目和股票的思路有相似之处,需要得到“净值”。我们首先把每一个加油站的油减去到下一个加油站的耗油量,得到剩余油量。那么我们从某个节点开始遍历,一路加每个加油站的剩余油量,当遇到车的油箱为负数的时候说明这个节点不能作为出发点。
这道题目可以解环来做,也可以利用while来循环。
三.代码
1.解环:
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int g = 0;
int index = 0;
vector<int> cur;
//可以通过将前n-1个节点压进数组将环解成线性的
for(int i=0;i<gas.size();i++)
cur.push_back(gas[i] - cost[i]);
for(int i=0;i<gas.size()-1;i++)
cur.push_back(gas[i] - cost[i]);
//开始进行遍历,遇到负数就从下一个节点重新遍历即可
while(index < gas.size()) {
for(int i=index;i<cur.size();i++) {
g += cur[i]; //累计油箱
if(g<0) { //如果油箱为负数,从下一个节点开始遍历
index = i + 1;
g = 0;
break;
}
if(i - index==gas.size()-1) return index; //开满全部节点数量就说明符合要求
}
}
return -1;
}
};