在一条环路上有 n 个加油站，其中第 i 个加油站有 gas[i] 升油，假设汽车油箱容量无限，从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。
请问能否绕环路行驶一周，如果可以则返回出发的加油站编号，如果不能，则返回 -1。
题目数据可以保证最多有一个答案。
数据范围： 
， gas 和 cost 数组中的值满足 
[编程题]加油站
题意整理
n个加油站排成一圈，每一个站点有对应的油，存储在gas数组，从一个站点走到下一个站点需要若干油量，存储在cost数组。
问能否绕环路行驶一周，如果可以则返回出发的加油站编号，如果不能，则返回-1。
方法一（枚举起始站点）
1.解题思路
首先枚举所有可能的起始加油站。如果剩余油量大于等
展开全文
题目的主要信息：
在一条环路上有 n 个加油站，其中第 i 个加油站有 gas[i] 升油，假设汽车油箱容量无限，从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。
请问能否绕环路行驶一周，如果可以则返回出发的加油站编号，如果不能，则返回 -1。
题目数据可以保证最多
展开全文
双指针
有油时候前指针可以前进（烧油），没油时候后指针必须后退（取油），直到两指针碰上。
如果最终油量大于０，可以跑足一圈，否则不能。
class Solution:
def gasStation(self ,
展开全文
思路: (算法的空间复杂度和时间复杂度都很高，但比较好理解的一种方法) 将每一个加油站看成是一个节点，所有的加油站，就构成了一个环形链表。然后，就以每一个加油站为起点，看是否能绕一圈。(注: 代码中的 HashMap 存放的是，每一个加油站所在的索引) 最后，就能找到最终的结果啦。
import
展开全文
刚开始尝试第一个开始（下标为0），last标记当前剩余油量
当l再次回到0的时候，表明没有方案，返回-1
当r == l的时候，表明有方案，返回l
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名
展开全文
描述
在一条环路上有 n 个加油站，其中第 i 个加油站有 gas[i] 升油，假设汽车油箱容量无限，从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。
请问能否绕环路行驶一周，如果可以则返
展开全文
题目主要信息
在一条环路上有 n 个加油站，其中第 i 个加油站有 gas[i] 升油，假设汽车油箱容量无限，从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。
请问能否绕环路行驶一周，如果可以则返回出发的加油站编号，如果不能，则返回 -1。
题目数据可以保证最多有一
展开全文
题意
一个环上，每经过第i个点，增加A[i]再减少B[i], 要求每个结果不小于零
限制：
环长度不大于10410^4104, 增减值不大于10510^5105
方法
枚举起点
直接按照题意，枚举所有起点.
对于每次枚举起点，模拟行驶一周，判断是否会出现油量为负的情况。
如果找到能让油量始终非负的起
展开全文
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param gas int整型vector
* @param cost int整型vec
展开全文
问题信息
难度：
9条回答
44收藏
1680浏览
通过挑战的用户
查看代码-
2022-09-17 10:07:35
-
2022-09-15 17:18:59
-
2022-09-15 08:14:59
-
2022-09-14 13:39:35 -
2022-09-14 01:34:36
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
