❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！
- 推荐：数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注
- 导航：
- LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
- 漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
- python源码解读：解读python的源代码与调用关系，快速提升代码质量
- python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
- 程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识
期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️
题目描述
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
注意：
- 如果存在解，则保证该解为唯一的。
示例 1:
输入: gas = [1,2,3,4,5] cost = [3,4,5,1,2] 输出: 3 解释: 从 3 号加油站开始，可以获得 4 升汽油。出发后，油箱里有 4 升汽油。 开往 4 号加油站需要 1 升汽油，剩余 3 升汽油。 开往 5 号加油站需要 2 升汽油，剩余 1 升汽油。 开往 1 号加油站需要 3 升汽油，剩余 -2 升汽油。 开往 2 号加油站需要 4 升汽油，剩余 -1 升汽油。 开往 3 号加油站需要 5 升汽油，剩余 -6 升汽油。 由于油箱里有足够的汽油可以完成环路，所以返回 3。
示例 2:
输入: gas = [2,3,4] cost = [3,4,3] 输出: -1 解释: 你只能从 0 号或 1 号加油站出发，但都不能完成环路行驶一周。
方法一：贪心算法
解题步骤
- 初始化总油量
total_tank和当前油量curr_tank为 0。 - 初始化起始站点
starting_station为 0。 - 遍历每个加油站，计算
total_tank和curr_tank分别增加当前站点的汽油量减去消耗量。 - 如果在某个站点
curr_tank小于 0，说明无法从当前starting_station到达该站点，因此需要将starting_station更新为该站点的下一个站点，并将curr_tank置为 0。 - 遍历结束后，如果
total_tank大于等于 0，返回starting_station，否则返回 -1。
Python 示例
def canCompleteCircuit(gas, cost): total_tank, curr_tank = 0, 0 starting_station = 0 for i in range(len(gas)): total_tank += gas[i] - cost[i] curr_tank += gas[i] - cost[i] if curr_tank < 0: starting_station = i + 1 curr_tank = 0 return starting_station if total_tank >= 0 else -1 # Example usage gas = [1, 2, 3, 4, 5] cost = [3, 4, 5, 1, 2] print(canCompleteCircuit(gas, cost)) # Output: 3 gas = [2, 3, 4] cost = [3, 4, 3] print(canCompleteCircuit(gas, cost)) # Output: -1
算法分析
- 时间复杂度：O(N)，其中 N 是加油站的数量。我们只需遍历一次所有的加油站。
- 空间复杂度：O(1)，只使用了常数级别的额外空间。
算法图解与说明
考虑 gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2] 总油量 total_tank = 0, 当前油量 curr_tank = 0, 起始站点 starting_station = 0 遍历每个加油站: 站点0: total_tank = -2, curr_tank = -2 (curr_tank < 0, 更新起始站点为1, curr_tank = 0) 站点1: total_tank = -4, curr_tank = -2 (curr_tank < 0, 更新起始站点为2, curr_tank = 0) 站点2: total_tank = -6, curr_tank = -2 (curr_tank < 0, 更新起始站点为3, curr_tank = 0) 站点3: total_tank = -3, curr_tank = 3 (curr_tank >= 0, 继续) 站点4: total_tank = 0, curr_tank = 4 (curr_tank >= 0, 继续) 总油量 total_tank >= 0，因此可以完成环路，返回起始站点3。
这种方法有效利用了贪心算法的思想，确保从正确的起始点开始能够完成环路行驶。
方法二：前缀和与一次遍历
解题步骤
- 初始化
total_tank和curr_tank为 0，用于计算总油量和当前油量。 - 初始化起始站点
starting_station为 0。 - 遍历每个加油站，计算从当前站点到下一个站点的油量差，并更新
total_tank和curr_tank。 - 如果在某个站点
curr_tank小于 0，说明无法从当前starting_station到达该站点。因此，将starting_station更新为该站点的下一个站点，并将curr_tank置为 0。 - 遍历结束后，如果
total_tank大于等于 0，说明有解，返回starting_station，否则返回 -1。
Python 示例
def canCompleteCircuit(gas, cost): total_tank, curr_tank = 0, 0 starting_station = 0 for i in range(len(gas)): total_tank += gas[i] - cost[i] curr_tank += gas[i] - cost[i] if curr_tank < 0: starting_station = i + 1 curr_tank = 0 return starting_station if total_tank >= 0 else -1 # Example usage gas = [1, 2, 3, 4, 5] cost = [3, 4, 5, 1, 2] print(canCompleteCircuit(gas, cost)) # Output: 3 gas = [2, 3, 4] cost = [3, 4, 3] print(canCompleteCircuit(gas, cost)) # Output: -1
算法分析
- 时间复杂度：O(N)，其中 N 是加油站的数量。只需遍历一次所有的加油站。
- 空间复杂度：O(1)，只使用了常数级别的额外空间。
算法图解与说明
考虑 gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2] 总油量 total_tank = 0, 当前油量 curr_tank = 0, 起始站点 starting_station = 0 遍历每个加油站: 站点0: total_tank = -2, curr_tank = -2 (curr_tank < 0, 更新起始站点为1, curr_tank = 0) 站点1: total_tank = -4, curr_tank = -2 (curr_tank < 0, 更新起始站点为2, curr_tank = 0) 站点2: total_tank = -6, curr_tank = -2 (curr_tank < 0, 更新起始站点为3, curr_tank = 0) 站点3: total_tank = -3, curr_tank = 3 (curr_tank >= 0, 继续) 站点4: total_tank = 0, curr_tank = 4 (curr_tank >= 0, 继续) 总油量 total_tank >= 0，因此可以完成环路，返回起始站点3。
这种方法与方法一的核心思想类似，但通过使用前缀和的概念更加简洁地实现了解决方案。核心在于每次从当前油量不足的地方重新开始计算起点，并最终判断总油量是否满足条件。
🌹🌹如果觉得这篇文对你有帮助的话，记得一键三连关注、赞👍🏻、收藏是对作者最大的鼓励，非常感谢 ❥(^_-)
❤️❤️作者知识有限，如有错误，请各位大佬评论区批评指正，不胜感激❥(^_-)
欢迎关注微信公众号 数据分析螺丝钉
