不绕圈是指,不需要看能不能转一圈回到起始点,只需要看能不能到达最后一个元素就行。
在做这一道题的时候,如果判断能不能回到出发点,则需要绕一圈再回来,不仅需要创建临时变量,还要频繁使用%n获得余数,非常的不优雅。下面是优化方法:
由题目很容易得出,如果存在解,则必定有gas总和大于或者等于cost总和。而且只要gas总和大于或者等于cost总和就一定有解,因为前面缺少的油,后面一定会多出一部分。
1.如果无解,即gas总和小于cost总和,直接返回-1。
2.如果有解,则进行如下操作:
从0开始遍历,如果能进入下一个点,则出发站不变;如果不能进入下一站,出发点更新为此时遍历点的下一位。
因为遍历过的这些点都不能作为出发站点。比如出发点为0,无法走到下标为4的点,那么从0-4之间的任何一个点作为出发点,都不可能到达4,因为0经过1-3这些点时会有燃油余量,说明在这个区间,从0出发已经是最好的选择了。
当i==n的时候,就说明从出发点可以达到最后一个加油站,直接跳出循环。不需要看能不能回到出发点,因为出发点之前的点都不行,出发点又是剩下的这些点里面的最优解,那就只能是他了。
最后返回出发点的位置p。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size();
int sum_gas = 0;
for (int i = 0; i < n; i++) {
sum_gas+=gas[i]-cost[i];
}
if (sum_gas < 0) {
return -1;
}
sum_gas = 0;
int p = 0;
for (int i = 0; i < n; i++) {
sum_gas += gas[i];
if (sum_gas < cost[i]) {
p = i + 1;
sum_gas = 0;
} else {
sum_gas -= cost[i];
}
}
return p;
}
};
标签:出发点,int,sum,gas,cost,绕圈,134,LeetCode,总和
From: https://blog.csdn.net/weixin_68169539/article/details/139883023