这题的意思就是求出从哪一个油站开始,能走完整个里程,并且这个结果是唯一的。
首先我们可以得到所有油站的油量totalGas,以及总里程需要消耗的油量totalCost,如果totalCost大于totalGas,那么铁定不能够走完整个里程。
如果totalGas大于totalCost了,那么就能走完整个里程了,假设现在我们到达了第i个油站,这时候还剩余的油量为sum,如果 sum + gas[i] - cost[i]小于0,我们无法走到下一个油站,所以起点一定不在第i个以及之前的油站里面(都铁定走不到第i + 1号油站),起点只能在i + 1后者后面。
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
int sum = 0;
int start = 0;
int total = 0;
for(int i = 0 ; i < gasSize; i++){
//i开始到下一站,油箱的油SUM是否>0
sum = sum+gas[i]-cost[i];
if(sum < 0) //没法到下一站,说明i之前开始的站都不可能走完,把开始位置暂定为i+1
{
start = i+1;
sum = 0;//sum为0 说明从i+1开始加油
}
//同时记录totalcost 和totalgas 如果totalgase-totalcost < 1 说明肯定没法走完
total = gas[i]-cost[i]+total;
}
if(total < 0)
return -1;
else
return start;
}