【算法与数据结构】134、LeetCode加油站
2023-12-21 11:31:09
所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。
一、题目
二、解法
??思路分析:用一张图就能说明本题的思路。首先,车能跑到下一个加油站必须是剩余油量大于耗油量,剩余油量=车剩余的油量+加油站的储量油。但是我们不需要用这个公式去计算。假设从第0个加油站出发,那么只要他剩余的油量大于0(车子初始油量为0),那么就可以到达下一个加油站。如下图所示,从零出发,能到第一个加油站(1+3>0),但到不了第二个加油站(1+3-6<0),那么车子不能从0号加油站出发,同理也不能从1,2号加油站出发。只能从3号或者往后的加油站出发。程序当中我们用tempSumOfLeftover来表示这个当前剩油量。此外,如果整体的加油站油量小于耗油量说明不可能跑完一圈,程序当中用SumOfLeftover表示。
??程序如下:
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int SumOfLeftover = 0, tempSumOfLeftover = 0; // 分别代表整体的剩余油量和当前的剩余油量
int start = 0; // 起始加油站下标,初始假设从第0个加油站出发
for (int i = 0; i < gas.size(); i++) {
SumOfLeftover += gas[i] - cost[i];
tempSumOfLeftover += gas[i] - cost[i];
if (tempSumOfLeftover < 0) { // 当前剩油量小于零说明必然不可能从start这个加油站出发
start = i + 1; // 更新start
tempSumOfLeftover = 0; // 置零
}
}
if (SumOfLeftover < 0) return -1; // 说明所有加油站的油量不足跑完一圈
return start;
}
};
复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n)。
- 空间复杂度: O ( 1 ) O(1) O(1)。
三、完整代码
# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int SumOfLeftover = 0, tempSumOfLeftover = 0; // 分别代表整体的剩余油量和当前的剩余油量
int start = 0; // 起始加油站下标,初始假设从第0个加油站出发
for (int i = 0; i < gas.size(); i++) {
SumOfLeftover += gas[i] - cost[i];
tempSumOfLeftover += gas[i] - cost[i];
if (tempSumOfLeftover < 0) { // 当前剩油量小于零说明必然不可能从start这个加油站出发
start = i + 1; // 更新start
tempSumOfLeftover = 0; // 置零
}
}
if (SumOfLeftover < 0) return -1; // 说明所有加油站的油量不足跑完一圈
return start;
}
};
int main() {
vector<int> gas = { 2,3,4 }; // 加油站的油量
vector<int> cost = { 3,4,3 }; // 开往下一个加油站的耗油量
//vector<int> gas = { 1,2,3,4,5 }; // 加油站的油量
//vector<int> cost = { 3,4,5,1,2 }; // 开往下一个加油站的耗油量
Solution s1;
int result = s1.canCompleteCircuit(gas, cost);
cout << result << endl;
system("pause");
return 0;
}
end
文章来源:https://blog.csdn.net/qq_45765437/article/details/135124166
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!