题目如下:
There are N gas stations along a circular route, where the amount of gas at station i is gas[i]
.
You have a car with an unlimited gas tank and it costs cost[i]
of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.hild.
我的提交:
/*17.3.31
*有点像最大连续子序列和的动态规划解法
*如果total大于0,从左到右扫描,一定能切分出一个和大于0的区间(起点为i,终点为数组的结尾)
*如-1,-2,2,3,-6,10
*-1被切开,-2被切开,3,4,-6被切开,10大于0,所以以10为起点!
*换一个顺序-6,10,-1,-2,2,3
*-6被切开,10~3大于0,结果还是以10为起点。
*/
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int start = 0,total = 0;
for(int i=0,tank=0;i<gas.length;i++){
if(tank<0){
tank = gas[i] - cost[i];
start = i;
}
else{
tank += gas[i] - cost[i];
}
total += gas[i] - cost[i];
}
return total<0?-1:start;
}
}