面试经典 150 个问题 - 加油站
最编程
2024-04-29 07:16:07
...
面试经典150题 day14
- 题目来源
- 我的题解
- 方法一 找最低点
- 方法二 贪心
题目来源
力扣每日一题;题序:134
我的题解
方法一 找最低点
参考 labuladong
找到最低点的下一个站 经过i之后变成最低点,则从i+1站开始
时间复杂度:O(n)
空间复杂度:O(1)
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n=gas.length;
int sum=0;
int start=0;
int minSum=0;
for(int i=0;i<n;i++){
sum+=gas[i]-cost[i];
if(sum<minSum){
// 经过第 i 个站点后,使 sum 到达新低
// 所以站点 i + 1 就是最低点(起点)
start=i+1;
minSum=sum;
}
}
if(sum<0){
// 总油量小于总的消耗,无解
return -1;
}
return start==n?0:start;
}
}
方法二 贪心
时间复杂度:O(n)
空间复杂度:O(1)
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n=gas.length;
int sum=0;
int start=0;
int myGas=0;
for(int i=0;i<n;i++){
sum+=gas[i]-cost[i];
myGas+=gas[i]-cost[i];
// 如果选择站点 start 作为起点「恰好」无法走到站点 i,那么 start 和 i 中间的任意站点 k 都不可能作为起点。只能从i+1开始重新寻找可以作为起点的位置
if(myGas<0){
start=i+1;
myGas=0;
}
}
if(sum<0){
return -1;
}
return start==n?0:start;
}
}
有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈????~
上一篇: 费雪信息和费雪信息矩阵
推荐阅读
-
LeetCode 面试经典 150 题 28.找出字符串中第一个匹配项的下标
-
[算法总结】13 个问题搞定 BAT 面试 - Strings
-
关于 PostgreSQL 的 20 个面试问题
-
Java 面试问题:解释 Java 中的并发工具类 ConcurrentHashMap 如何工作,并列举经典应用示例
-
10 个经典图像处理面试问题(附答案)!
-
面试经典 150 个问题 - 加油站
-
[ElasticSearch 面试] 你必须知道的 10 个 ElasticSearch 面试问题
-
面试问题:确定一个完全平方数
-
10 SQL 高级 -- 综合练习题 -- 10 个经典 SQL 问题,附带数据和答案
-
50 个 Python 面试基本问题汇总(附答案)