【算法与数据结构】134、LeetCode加油站

发布时间:2023年12月21日

所有的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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。