[leetcode]gas-station加油站（贪心）

缺乏、安全感 2022-03-11 13:25 231阅读 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.

## 解决思路： ##

将start放在最后一个加油站，end放在第一个。从start出发，如果油量可以走到下一站，就向后走（end++，代表耗油），如果油量不够了，start要向后退（start--，代表去加油）。如果start和end重合的时候还有油（>=0），题目又规定了一定是唯一解，这就说明当前start位置就是要求的位置，如果油量不够（<0）则无解，返回-1。

## 具体实现： ##

class Solution {
    public:
        int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
            int start = gas.size()-1;
            int end = 0;
            int sum = gas[start] - cost[start];
            while(start > end){
                if(sum > 0){
                    sum += gas[end];
                    sum -= cost[end];
                    end++;
                }else{
                    start--;
                    sum += gas[start];
                    sum -= cost[start];
                }
            }
            return (sum >= 0)? start : -1;
        }
    };

参考了大神们的做法，真的巧妙！继续加油鸭，编程能力会变好的！会变强的！

发表评论取消回复

表情：

评论列表（有 0 条评论，231人围观）

还没有评论，来说两句吧...

相关阅读

相关 134. 加油站（JS实现）

1 题目 > 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas\[i\] 升。 > 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个

布满荆棘的人生/ 2023年03月04日 08:14/ 0 赞/ 8 阅读

相关加油站[134]

加油站\[134\] 题目题解题目在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas\[i\] 升。你有一辆油箱容量无限的的汽

今天药忘吃喽~/ 2023年02月26日 15:22/ 0 赞/ 112 阅读

相关 C语言经典贪心算法之加油站问题（详解）

文章目录一、贪心算法二、加油站问题一、贪心算法贪心算法暗示一种不追求最优解，只希望找到较为满意解的方法。贪心算法省去了为找最优解

ゝ一纸荒年。/ 2023年01月11日 01:27/ 0 赞/ 303 阅读

相关（js）leetcode 134. 加油站

人吧，总是会在不断学习的过程中发现自己是多么的无知，好吧，我说的是我自己。做完题，再去看别人的解题思路，发现自己的知识储备真的是太少了，数据结构与算法得看起来了，否则只寄希

系统管理员/ 2022年12月22日 08:59/ 0 赞/ 130 阅读

相关 leetcode143题加油站

leetcode143题加油站题目描述在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas\[i\] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油

刺骨的言语ヽ痛彻心扉/ 2022年12月18日 06:00/ 0 赞/ 156 阅读

相关 134. 加油站

> > 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas\[i\] 升。 > > 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油

忘是亡心i/ 2022年10月06日 15:54/ 0 赞/ 158 阅读

相关 leetcode 134 加油站

前言题目：[134. 加油站][134.] 参考题解：[加油站-代码随想录][-] -------------------- 提交代码方法一：暴力法。均从

分手后的思念是犯贱/ 2022年08月28日 09:47/ 0 赞/ 176 阅读

相关【LeetCode】134. 加油站

题目链接：[https://leetcode-cn.com/problems/gas-station/description/][https_leetcode-cn.com_p

「爱情、让人受尽委屈。」/ 2022年05月10日 15:10/ 0 赞/ 182 阅读

相关加油站问题

\include<iostream> using namespace std; //加油站问题 int main()\{ int a\[1005\],n,

古城微笑少年丶/ 2022年05月10日 14:14/ 0 赞/ 230 阅读

相关 [leetcode]gas-station加油站（贪心）

问题描述： There are N gas stations along a circular route, where the amount of gas at sta

缺乏、安全感/ 2022年03月11日 13:25/ 0 赞/ 232 阅读