Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >Leetcode 134 Gas Station

Leetcode 134 Gas Station

作者头像
triplebee
发布于 2018-01-12 06:52:28
发布于 2018-01-12 06:52:28
59500
代码可运行
举报
运行总次数:0
代码可运行

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note: The solution is guaranteed to be unique.

贪心,我的做法是将gas-cost的值求和,和小于0,则肯定不能到,大于等于0一定可以到,因为一定可以从无法通过的那段区域的下一个位置开始。

求出gas-cost和最小的位置,那么从他的下一个位置开始,必定可以通过。

然后在discuss看到了更好的做法:是否可达和我的一样,但是起始位置和我的想法不一样,

一旦发现和小于0,则把它下一个位置置为起始位置,更新tank为0,最后得到的起始位置就是结果。

因为每发现和小于0,则可以把这些加油站看作一个加油站,一直到最后只有两个两个加油站,后一个加前一个必然大于等于0!

有可能没说清楚,贴上英文原文解释:

Proof to the first point: say there is a point C between A and B -- that is A can reach C but cannot reach B. Since A cannot reach B, the gas collected between A and B is short of the cost. Starting from A, at the time when the car reaches C, it brings in gas >= 0, and the car still cannot reach B. Thus if the car just starts from C, it definitely cannot reach B.

Proof for the second point:

  • If there is only one gas station, it’s true.
  • If there are two gas stations a and b, and gas(a) cannot afford cost(a), i.e., gas(a) < cost(a), then gas(b) must be greater than cost(b), i.e., gas(b) > cost(b), since gas(a) + gas(b) > cost(a) + cost(b); so there must be a way too.
  • If there are three gas stations a, b, and c, where gas(a) < cost(a), i.e., we cannot travel from a to b directly, then:
  • either if gas(b) < cost(b), i.e., we cannot travel from b to c directly, then cost(c) > cost(c), so we can start at c and travel to a; since gas(b) < cost(b), gas(c) + gas(a) must be greater than cost(c) + cost(a), so we can continue traveling from a to b. Key Point: this can be considered as there is one station at c’ with gas(c’) = gas(c) + gas(a) and the cost from c’ to b is cost(c’) = cost(c) + cost(a), and the problem reduces to a problem with two stations. This in turn becomes the problem with two stations above.
  • or if gas(b) >= cost(b), we can travel from b to c directly. Similar to the case above, this problem can reduce to a problem with two stations b’ and a, where gas(b’) = gas(b) + gas(c) and cost(b’) = cost(b) + cost(c). Since gas(a) < cost(a), gas(b’) must be greater than cost(b’), so it’s solved too.
  • For problems with more stations, we can reduce them in a similar way. In fact, as seen above for the example of three stations, the problem of two stations can also reduce to the initial problem with one station.
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int sum = 0, minn = INT_MAX, pos;
        for(int i = 0;i < gas.size();i++)
        {
            sum+=(gas[i]-cost[i]);
            if(minn > sum)
            {
                minn = sum;
                pos = i;
            }
        }
        if(sum<0) return -1;
        return (pos+1) % gas.size();
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-11-03 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
【LEETCODE】模拟面试-134-Gas Station
新生 题目: https://leetcode.com/problems/gas-station/ There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its
杨熹
2018/04/03
7770
【LEETCODE】模拟面试-134-Gas Station
LeetCode 134. Gas Station题目分析
There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the starting gas station's index if you can travel around the circuit once, otherwise return -1. Note:The solution is guaranteed to be unique. Subscribe to see which companies asked this question. 在一条环路上有 N 个加油站,其中第 i 个加油站有汽油gas[i],并且从第i个加油站前往第i+1个加油站需要消耗汽油cost[i]。 你有一辆油箱容量无限大的汽车,现在要从某一个加油站出发绕环路一周,一开始油箱为空。 求可环绕环路一周时出发的加油站的编号,若不存在环绕一周的方案,则返回-1。 注意事项 数据保证答案唯一。 样例 现在有4个加油站,汽油量gas[i]=[1, 1, 3, 1],环路旅行时消耗的汽油量cost[i]=[2, 2, 1, 1]。则出发的加油站的编号为2。
desperate633
2018/08/22
7380
LeetCode 0134 - Gas Station
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
Reck Zhang
2021/08/11
3230
[LeetCode] 134. Gas Station
本文讨论了一种算法题的解题思路,通过计算每个站点的差和,从第一个差和不为负数的站点开始环游,并返回起始站点。
用户1148830
2018/01/03
6270
​LeetCode刷题实战134:加油站
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
程序员小猿
2021/02/01
3740
​LeetCode刷题实战134:加油站
回溯/贪心高频题
"有关递归的算法,都离不开“树”的遍历这一抽象模型。只不过对于不同的算法,在前(中)后序遍历的时候,所做的事不同而已。 "
王脸小
2019/10/28
1.4K0
PAT 1033 To Fill or Not to Fill (25分) 贪心思想
With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.
vivi
2020/07/14
7050
LeetCode 134 Gas Station
LeetCode 134 Gas Station 水题,暴力一下就ok class Solution { public: int tag[100005]; int sum[100005]; int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int l = gas.size(); for(int i=0;i<l;i++) { ta
ShenduCC
2018/12/12
4220
【Codeforces 738C】Road to Cinema
http://codeforces.com/contest/738/problem/C
饶文津
2020/06/02
4100
[Leetcode][python]Gas Station/加油站
贪心法。但其实需要证明,证明详见: http://bookshadow.com/weblog/2015/08/06/leetcode-gas-station/ 看懂证明,才能看懂代码
蛮三刀酱
2019/03/26
6850
LeetCode 134. 加油站(贪心)
你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。
Michael阿明
2020/07/13
7280
LeetCode 134. 加油站(贪心)
贪心算法-LeetCode 134、111(递归算法,异或性质,贪心)
对于swap函数使用中间变量的形式大家都不陌生了,但是对于面试官来说这种方法不出奇,并不是面试官想要的!有没有不使用中间变量的呢? 在swap2函数中,我们可以使用这样的方式来交换a和b的值,但是swap2函数有一个缺陷就是,a+b有可能会造成数据溢出!!! 在swap3函数中,使用异或来进行a和b的交换,关于异或的性质如下: 假设有A, B, C三个数,C 相等于 A ^ B, 则必定 A ^ C 相等于 B, B ^ C 相等于 A
算法工程师之路
2019/10/24
7300
134. 加油站(前缀和+单调队列|贪心)「建议收藏」
你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。
全栈程序员站长
2022/09/22
2310
加油站,能怎么贪心?
力扣题目链接:https://leetcode-cn.com/problems/gas-station
代码随想录
2021/11/23
4420
leetcode-134-加油站
你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。
chenjx85
2018/09/29
4550
【leetcode刷题】T174-加油站
你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。
木又AI帮
2019/10/03
3910
leetcode每日一题:134 加油站
题目地址: https://leetcode-cn.com/problems/gas-station/
用户3578099
2020/11/30
8740
leetcode每日一题:134 加油站
187. 加油站贪心
在一条环路上有 N 个加油站,其中第 i 个加油站有汽油gas[i],并且从第i个加油站前往第i+1个加油站需要消耗汽油cost[i]。 你有一辆油箱容量无限大的汽车,现在要从某一个加油站出发绕环路一周,一开始油箱为空。 求可环绕环路一周时出发的加油站的编号,若不存在环绕一周的方案,则返回-1。
和蔼的zhxing
2018/09/04
5170
LeetCode 题目解答——Medium 部分(上)
[Updated on 9/22/2017] 如今回头看来,里面很多做法都不是最佳的,有的从复杂度上根本就不是最优解,有的写的太啰嗦,有的则用了一些过于 tricky 的方法。我没有为了这个再更新,就让它们去吧。
四火
2022/07/19
6570
LeetCode 题目解答——Medium 部分(上)
Leetcode No.134 加油站
在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。 如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1。
week
2022/01/06
2810
Leetcode No.134 加油站
相关推荐
【LEETCODE】模拟面试-134-Gas Station
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验