Gas Station
这道题就是说连续的gas station(加气站么...),在i gas station可以获取gas[i] of gas, 可是开到下一个gas station (i + 1)要消耗 cost[i] of gas. 题目给定一圈gas station,问从哪个gas station出发可以走完一圈,走不完的话返回-1
下面的solution,start是最后一个index,end是0,这样做是因为最后的结果start是起始点。从start(最后一个index)开始,求出开到下一个gas station后剩余gas的量,也就是gas[start] - cost[start]。然后根据sum的正负号判断是否能开到下一个(老司机开车咯 唔),如果不可以的话(sum为负),start--,加上前面剩余的gas,。如果可以的话,现在的sum减去end开车到下一个加油站的剩余量。循环
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int start(gas.size() - 1), end(0);
int sum(gas[start] - cost[start]);
while (start > end) {
if (sum < 0) {
start--;
sum += gas[start] - cost[start];
} else {
sum += gas[end] - cost[end];
end++;
}
}
return sum >= 0 ? start : -1;
}
};
网友评论