首页 > 试题广场 >

加油站

[编程题]加油站
  • 热度指数：33763 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
环形路上有n个加油站，第i个加油站的汽油量是gas[i].
你有一辆车，车的油箱可以无限装汽油。从加油站i走到下一个加油站（i+1）花费的油量是cost[i]，你从一个加油站出发，刚开始的时候油箱里面没有汽油。
求从哪个加油站出发可以在环形路上走一圈。返回加油站的下标，如果没有答案的话返回-1。
注意：
答案保证唯一。
示例1

输入

[2,3,1],[3,1,2]

输出

1
算法知识视频讲解
开通博客
头像 华科不平凡
发表于 2020-08-10 15:20:33
突破点：如果到某个加油站剩余油量不足0，就从下一个加油站重新开始。 class Solution { public: /** * * @param gas int整型vector * @param cost int整型vector * @return 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 胖胖不吹牛
发表于 2020-03-19 22:53:00
构建剩余油数组；res为相同的两个剩余油数组连接在一起，方便遍历。指针i指初始加油站。指针j<len+i向后指；剩余油取和。若到加油站剩余油小于0，将更新指针i到词加油站+1的位置。 public class Solution { public int canCompleteCircu 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 最喜欢春天的大白菜很糊涂
发表于 2024-09-23 17:14:38
# # # @param gas int整型一维数组 # @param cost int整型一维数组 # @return int整型 # class Solution: def canCompleteCircuit(self , gas , cost ): # writ 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 GoodLuck490332048
发表于 2022-08-04 11:08:57
class Solution:     def canCompleteCircuit(self , gas , cost ):  # 走一圈的意思是从某个加油站 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 栖岁
发表于 2025-03-13 14:37:36
class Solution { public: /** * * @param gas int整型vector * @param cost int整型vector * @return int整型 */ int canComple 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 FLOYD20191121155229
发表于 2024-09-23 11:08:26
要解决这个问题，我们可以使用贪心算法。我们需要从每个加油站出发，判断是否能够绕环形路线行驶一圈。以下是解决思路和代码实现。思路初始化变量：定义两个变量，total_tank 用于记录总体的汽油差（总的油量减去总的消耗），current_tank 用于记录当前油量差；还需要一个 start 变量记录可 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 最喜欢春天的大白菜很糊涂
发表于 2024-09-23 17:07:48
# # # @param gas int整型一维数组 # @param cost int整型一维数组 # @return int整型 # class Solution: def canCompleteCircuit(self , gas , cost ): # writ 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

贪心
难度：
140条回答 36952浏览

热门推荐

通过挑战的用户

查看代码

相关试题

加油站

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号