返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C++实现LeetCode(134.加油站问题)
  • 883
分享到

C++实现LeetCode(134.加油站问题)

2024-04-02 19:04:59 883人浏览 独家记忆
摘要

[LeetCode] 134.Gas Station 加油站问题 There are N gas stations along a circular route,

[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.

这道转圈加油问题不算很难,只要想通其中的原理就很简单。我们首先要知道能走完整个环的前提是gas的总量要大于cost的总量,这样才会有起点的存在。假设开始设置起点start = 0, 并从这里出发,如果当前的gas值大于cost值,就可以继续前进,此时到下一个站点,剩余的gas加上当前的gas再减去cost,看是否大于0,若大于0,则继续前进。当到达某一站点时,若这个值小于0了,则说明从起点到这个点中间的任何一个点都不能作为起点,则把起点设为下一个点,继续遍历。当遍历完整个环时,当前保存的起点即为所求。代码如下:

解法一:


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

我们也可以从后往前遍历,用一个变量mx来记录出现过的剩余油量的最大值,total记录当前剩余油量的值,start还是记录起点的位置。当total大于mx的时候,说明当前位置可以作为起点,更新start,并且更新mx。为啥呢?因为我们每次total加上的都是当前位置的油量减去消耗,如果这个差值大于0的话,说明当前位置可以当作起点,因为从当前位置到末尾都不会出现油量不够的情况,而一旦差值小于0的话,说明当前位置如果是起点的话,油量就不够,无法走完全程,所以我们不更新起点位置start。最后结束后我们还是看totoa是否大于等于0,如果其小于0的话,说明没有任何一个起点能走完全程,因为总油量都不够,参见代码如下:

解法二:


class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total = 0, mx = -1, start = 0;
        for (int i = gas.size() - 1; i >= 0; --i) {
            total += gas[i] - cost[i];
            if (total > mx) {
                start = i;
                mx = total;
            }
        }
        return (total < 0) ? -1 : start;
    }
};

类似题目:

Reaching Points

TransfORM to Chessboard

Cheapest Flights Within K Stops

参考资料:

https://leetcode.com/problems/gas-station/discuss/42568/Share-some-of-my-ideas.

Https://leetcode.com/problems/gas-station/discuss/42656/8ms-simple-O(n)-c++-solution

到此这篇关于C++实现LeetCode(134.加油站问题)的文章就介绍到这了,更多相关C++实现加油站问题内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

--结束END--

本文标题: C++实现LeetCode(134.加油站问题)

本文链接: https://www.lsjlt.com/news/131269.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • C++实现LeetCode(134.加油站问题)
    [LeetCode] 134.Gas Station 加油站问题 There are N gas stations along a circular route,...
    99+
    2024-04-02
  • C++实现LeetCode之加油站问题的示例分析
    这篇文章主要介绍C++实现LeetCode之加油站问题的示例分析,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完![LeetCode] 134.Gas Station 加油站问题There are N ...
    99+
    2023-06-20
  • C++实现LeetCode(51.N皇后问题)
    [LeetCode] 51. N-Queens N皇后问题 The n-queens puzzle is the problem of placing n...
    99+
    2024-04-02
  • C++实现LeetCode(70.爬楼梯问题)
    [LeetCode] 70. Climbing Stairs 爬楼梯问题 You are climbing a stair case. It takes n st...
    99+
    2024-04-02
  • C++实现LeetCode(135.分糖果问题)
    [LeetCode] 135.Candy 分糖果问题 There are N children standing in a line. Each child is...
    99+
    2024-04-02
  • C++实现LeetCode(52.N皇后问题之二)
    [LeetCode] 52. N-Queens II N皇后问题之二 The n-queens puzzle is the problem of placing ...
    99+
    2024-04-02
  • C++实现LeetCode(66.加一运算)
    [LeetCode] 66. Plus One 加一运算 Given a non-empty array of decimal digits repre...
    99+
    2024-04-02
  • C++实现LeetCode数组练习题
    目录1、存在重复元素2、最大子序和3、两数之和4、合并两个有序数组5、两个数组的交集II6、买卖股票的最佳时机7、杨辉三角8、重塑矩阵9、有效的数独10、矩阵置零总结1、存在重复元素...
    99+
    2024-04-02
  • C++实现LeetCode(2.两个数字相加)
    [LeetCode] 2. Add Two Numbers 两个数字相加 You are given two non-empty linked lists rep...
    99+
    2024-04-02
  • C++实现LeetCode(67.二进制数相加)
    [LeetCode] 67. Add Binary 二进制数相加 Given two binary strings a and b, return...
    99+
    2024-04-02
  • C++如何实现LeetCode两个数字相加
    这篇文章将为大家详细讲解有关C++如何实现LeetCode两个数字相加,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。[LeetCode] 2. Add Two Numbers 两个数字相加You are ...
    99+
    2023-06-20
  • C++实现LeetCode(241.添加括号的不同方式)
    [LeetCode] 241. Different Ways to Add Parentheses 添加括号的不同方式 Given a string of numbers and o...
    99+
    2024-04-02
  • c语言循环加数组实现汉诺塔问题
    目录简介递归的汉诺塔解法(c语言)循环实现汉诺塔问题(c语言)简介 汉诺塔问题是学数据结构与算法的时候会遇到的问题,相信来看本文的读者应该都对汉诺塔问题有基本的了解,理论上所有的递归...
    99+
    2024-04-02
  • C++实现LeetCode之添加和查找单词的示例分析
    这篇文章将为大家详细讲解有关C++实现LeetCode之添加和查找单词的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。[LeetCode] 211.Add and Search Word - Da...
    99+
    2023-06-20
  • C++约瑟夫环问题怎么实现
    本文小编为大家详细介绍“C++约瑟夫环问题怎么实现”,内容详细,步骤清晰,细节处理妥当,希望这篇“C++约瑟夫环问题怎么实现”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。题目如下:有一家公司,这个公司有一位老板和...
    99+
    2023-06-26
  • C语言实现24点问题详解
    目录题目描述问题分析代码实现运行结果题目描述 在屏幕上输入1〜10范围内的4个整数(可以有重复),对它们进行加、减、乘、除四则运算后(可以任意的加括号限定计算的优先级),寻找计算结果...
    99+
    2024-04-02
  • C++实现LeetCode(211.添加和查找单词-数据结构设计)
    [LeetCode] 211.Add and Search Word - Data structure design 添加和查找单词-数据结构设计 Design a data str...
    99+
    2024-04-02
  • C#实现分治算法求解股票问题
    目录分治策略是:可使用分治法求解的一些经典问题分治算法 - 最大子数组问题 (1)暴力求解(2)分治法分治法实现大数相乘 C#实现分治策略是: 对于一个规模为n的问题,若该...
    99+
    2024-04-02
  • C++怎么实现水果装入果篮问题
    这篇文章主要介绍“C++怎么实现水果装入果篮问题”,在日常操作中,相信很多人在C++怎么实现水果装入果篮问题问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”C++怎么实现水果装入果篮问题”的疑惑有所帮助!接下来...
    99+
    2023-06-20
  • C语言版约瑟夫问题算法实现
    1、问题描述:        有n个人围坐一圈,现从第s个人开始报数,数到m的人出列,接着从出列的下一个人开始重新报数,数到m的人又出列.如此下去,直到所有人都出列为止.试设计确定他...
    99+
    2024-04-02
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作