暴力求解
解题思路
for 循环 适合模拟从头到尾的遍历，而 while 循环 适合模拟环形遍历；
第一层 for 循环 用于模拟出发的起点；
第二层 while 循环 用于判断，是否能跑完完整的一圈；
复杂度
-
时间复杂度：
O(n^2)； -
空间复杂度：
O(1)；
代码实现
var canCompleteCircuit = function (gas, cost) {
for (let i = 0; i < gas.length; i++) {
// 1. 第一天，从 i 点出发
let rest = gas[i] - cost[i]; // 记录剩余油量
let index = (i + 1) % gas.length; // 下一天的起点
// 2. 模拟以 i 为起点行驶一圈（如果有rest==0，那么答案就不唯一了）
while (rest > 0 && index !== i) {
rest += gas[index] - cost[index]; // 更新剩余油量
index = (index + 1) % gas.length; // 下一天的起点
}
// 3. 如果以 i 为起点跑一圈，剩余油量 >=0，返回该起始位置
if (rest >= 0 && index == i) return i;
}
return -1;
};
贪心
解题思路
如果总油量减去总消耗大于等于零那么一定可以跑完一圈，因此要跑完一圈就要保证在各个站点的加油站 剩油量
rest[i] >= 0；具体思路：
- 遍历数组 i 从 0 开始累加 rest[i] ，和记为 curSum；
- 计算每个加油站的剩余量
curSum += gas[i] − cost[i]；- 若 curSum 小于零，说明 [0, i] 区间都不能作为起始位置，起始位置从 i+1 算起，curSum 清零重新计算；
复杂度
-
时间复杂度：
O(n)； -
空间复杂度：
O(1)；
代码实现
var canCompleteCircuit = function (gas, cost) {
let totalSum = 0; // 总剩余油量
let curSum = 0; // 当前起点总剩余油量
let start = 0; // 起点
// 从每个起点开始模拟，是否能跑完全程
for (let i = 0; i < gas.length; i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
// 若 curSum 小于零，说明 [0, i] 区间都不能作为起始位置，起始位置从 i+1 算起，curSum 清零重新计算
if (curSum < 0) {
curSum = 0;
start = i + 1;
}
}
// 如果剩余总油量为负数，则一定无法跑完全程
if (totalSum < 0) return -1;
return start;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 459. 重复的子字符串
上一篇
评论
