加油站
程序员文章站
2022-07-15 12:47:15
...
题目
来源:力扣(LeetCode)
链接:加油站
解法一
使用二重循环, 从0到gasSize枚举i,从第i个加油站出发枚举,若可以到达下一个加油站,令j=i+1,记下每到下一个站剩下的油量,若油量小于0.,则无法绕环路一周,退出该层循环,否则开往下一个加油站。循环至j==i。
时间复杂度为O(n2)
代码
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
int curgas=0;
for(int i=0;i<gasSize;i++){
curgas=gas[i]-cost[i]; //能否达到第i+1个加油站
if(curgas<0) continue;// 从第i个加油站出发无法绕环路一周
int j=(i+1)%gasSize;
while(j!=i){
curgas=curgas+gas[j]-cost[j];//开往下一个加油站剩下的油量
if(curgas<0)
break; //无法到达下一个加油站
j=(j+1)%gasSize;
}
if(j==i)
return i;
}
return -1;
} // o(n^2) 的复杂度
解法二
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
int curGas=0;
int sumRemainGas=0;
int st=0;
for(int i=0;i<gasSize;i++){
sumRemainGas+=gas[i]-cost[i];
curGas+=gas[i]-cost[i]; //存储从st站出发到第i+1站台剩下的油量
if(curGas<0){
st=i+1;
curGas=0;
}
}
if(sumRemainGas>=0)
return st;
else
return -1;
} // o(n) 的复杂度