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

[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++实现加油站问题内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(127.词语阶梯)

    [LeetCode] 127.Word Ladder 词语阶梯 Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that: Only one letter can be changed at a time. Each transforme

  • C++实现LeetCode(200.岛屿的数量)

    [LeetCode] 200. Number of Islands 岛屿的数量 Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four

  • C++实现LeetCode(124.求二叉树的最大路径和)

    [LeetCode] 124. Binary Tree Maximum Path Sum 求二叉树的最大路径和 Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child conn

  • C++实现LeetCode(126.词语阶梯之二)

    [LeetCode] 126. Word Ladder II 词语阶梯之二 Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that: Only one letter can be changed at a time Each transformed

  • C++验证LeetCode包围区域的DFS方法

    验证LeetCode Surrounded Regions 包围区域的DFS方法 在LeetCode中的Surrounded Regions 包围区域这道题中,我们发现用DFS方法中的最后一个条件必须是j > 1,如下面的红色字体所示,如果写成j > 0的话无法通过OJ,一直百思不得其解其中的原因,直到有网友告诉我说他验证了最后一个大集合在本地机子上可以通过,那么我也来验证看看吧. class Solution { public: void solve(vector<vector<

  • C++实现LeetCode(130.包围区域)

    [LeetCode] 130. Surrounded Regions 包围区域 Given a 2D board containing 'X' and 'O'(the letter O), capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. Example: X X X X X O O X X X O X X O

  • C++实现LeetCode(129.求根到叶节点数字之和)

    [LeetCode] 129. Sum Root to Leaf Numbers 求根到叶节点数字之和 Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum

  • C++实现LeetCode(128.求最长连续序列)

    [LeetCode] 128.Longest Consecutive Sequence 求最长连续序列 Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity. Example: Input: [100, 4, 200, 1, 3, 2] Output: 4 Expl

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

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

  • C++实现LeetCode(23.合并k个有序链表)

    [LeetCode] 23. Merge k Sorted Lists 合并k个有序链表 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6 这

  • C++实现LeetCode(21.混合插入有序链表)

    [LeetCode] 21. Merge Two Sorted Lists 混合插入有序链表 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Example: Input: 1->2->4, 1->3->4 Output: 1->1->2

  • LeetCode -- Path Sum III分析及实现方法

    LeetCode -- Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards

  • 基于Java实现杨辉三角 LeetCode Pascal's Triangle

    基于Java实现杨辉三角 LeetCode Pascal's Triangle

    Pascal's Triangle Given numRows, generate the first numRows of Pascal's triangle. For example, given numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 这道题比较简单, 杨辉三角, 可以用这一列的元素等于它头顶两元素的和来求. 数学扎实的人会看出, 其实每一列都是数学里的排列组合, 第4行, 可以用 C30 =

  • 天下·网吧加油站打造稳定的电子交易平台

    "天下·网吧加油站":打造稳定的电子交易平台 中国电子商务市场的发展有目共睹,其发展速度之快.覆盖范围之广完全超越了人们想象的空间.然而,基于安全性与稳定性的考虑,传统的电子商务一直采取"鼠标加水泥"的方式,网上达成交易,网下进行物流,并使用传统的付款方式实现最后一个环节.这种方式对于传统行业的电子商务来说,应该可以理解,但如果放到网游市场上来看,就显得颇为尴尬了.鉴于此,一旦当天下·网吧加油站.骏网.云网等第三方电子交易平台解决了安全性和稳定性问题后,附着于网游产

  • vscode中配置LeetCode插件的教程(愉快刷题)

    大家好,今早在B站看到up主的vscode里藏了leetcode插件,这才知道原来还有这款神器.但是没想到在用的时候遇到了一些麻烦,花了一点时间才解决.所以写这篇文章除了给大家安利这个好用的插件之外,也是为了帮助更多的同学避免踩坑. 简介vscode vscode在工业界鼎鼎大名,被誉为微软少有的拿得出手的精品(逃).原本是不想过多赘述的,但是鉴于许多粉丝还是正在上学的萌新,所以花点笔墨简单介绍一下. vscode是微软开发的编辑器,严格说起来它并不是一个IDE,只是一个编辑器.但是由于它支持嵌

  • vscode+leetcode环境配置方法

    前言 之前安装anaconda3的时候,选择了同时安装vscode,但从来没有正式去接触过它.最近,偶然想到看看leetcode,发现在vscode上搞leetcode很方便,于是就开始倒腾起来了. vscode配置 如何安装我就不详述了,win/ubuntu下的安装可参见我的博客: vscode+python+c++ 我现在的vscode的版本是:1.43.1 需要安装的插件有: anaconda extension pack: 支持非python官方的三方库code runner:F5快捷运

  • vscode配置leetcode插件并解决无法登录问题(图文详解)

    官方文档 https://github.com/LeetCode-OpenSource/vscode-leetcode/blob/master/docs/README_zh-CN.md 1.环境 window10 vscode 1.23.0+ Node.js 10+ 如果Node.js 没添加到环境变量需要手动添加,添加成功在cmd中输入node --version会显示:  2.配置 vscode安装leetcode插件: 安装完右侧会出现: 此时发现账号密码方式无法登录(本次教程都针对国际版

  • 如何在Intellij中安装LeetCode刷题插件方便Java刷题

    一.安装 在 IDEA(2019)的 setting 的 Plugins 的 Marketplace 中搜索 leetcode,即可以找到该插件,安装完成了,重启即可. 二.配置 1.重启完成后,第一次使用的时候,需要一些基本的配制,在 setting 中的 Tools 中可以找到该插件工具,为 leetcode plugin,在里面,可以选择访问的为国际的 LeetCode 还是国内的,以及何种语言,同时,输入自己账户名(LoginName)和密码(Password),则可以和自己帐号关联起来

随机推荐