`
cozilla
  • 浏览: 92074 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

[Leetcode] Gas Station

 
阅读更多

Gas Station

 
AC Rate: 1017/4717
My Submissions

 

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.

similar with max range sum.

 

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int n = gas.size();
        vector<int> v(n);
        for (int i = 0; i < n; i++) v[i] = gas[i] - cost[i];
        int s = 0, e = 0, t = 0;
        while (s < n) {
            while (t >= 0 && e < s + n) t += v[(e++) % n];
            if (t >= 0 && e == s + n) return s;
            t -= v[s];
            s++;
        }
        return -1;
    }
};

 

分享到:
评论

相关推荐

    java-leetcode题解之Gas Station.java

    java java_leetcode题解之Gas Station.java

    python-leetcode题解之134-Gas-Station

    python python_leetcode题解之134_Gas_Station

    js-leetcode题解之134-gas-station.js

    javascript js_leetcode题解之134-gas-station.js

    gasstationleetcode-leetcode:简单纪录每日一题

    gas station leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9...

    gasstationleetcode-LeetCode_Practice:我的LeetCode练习从2020年开始

    134_Gas_Station 118_Pascal's_Triangle_I 119_Pascal's_Triangle_II 169_Majority_Element 229_Majority_Element_II 274_H_索引 275_H_Index_II 217_Contain_Duplicate 55_Jump_Game 45_Jump_Game_II 121_Best_Time...

    gasstationleetcode-leetcode_c:leetcode一些题目的C语言解答

    这道题,题目名字就叫gas-station(网址的最后一部分),于是此题目的代码也在gas-station.c文件中。 当一道题通过测试且性能达到预期时,将在git中commit,注释为“测试通过,性能达标”。若commit的注释为其它内容...

    gasstationleetcode-leetcode-in-niuke:在牛客网上的在线编程中的leetcode在线编程题解

    gas ...gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归 valid-palindrome 模拟 pascals-triangle 模拟 pasca

    gasstationleetcode-leetcode:LeetcodeOJ解决方案

    leetcode 【演示记录】 报告 展示 2017/03/06 1.二和,167.二和二 2107/03/06 15.3 总和,16.3 总和最近,18.4 总和,11.最多水的容器 2017/03/09 62.Unique Paths, 63.Unique Paths II, 64.Minimum Path Sum 2017/...

    Leetcode题目+解析+思路+答案.pdf

    - **Gas Station**:寻找最短的加油路线。 - **Candy**:分糖果,确保每个孩子至少得到一块糖,尽可能公平。 - **Word Break**:判断一个字符串是否可以拆分为一个词汇表中的单词序列。 7. **链表(Linked List...

    gasstationleetcode-Leetcode:力码

    Leetcode\gas station(134)。 swift Leetcode\group anagrams(49).swift Leetcode\group 给定他们所属的组大小的人(1282).swift Leetcode\数组中的第k 个最大元素(215).swift Leetcode\最长递增子序列(300).swift ...

    LeetCode leetcode部分题解答代码实现

    * Gas Station:给定一个数组,返回可以到达的加油站数量。这个题目需要使用贪心算法的思想,将数组分解成更小的子数组,并统计可以到达的加油站数量。 7. 链表 链表是一种非常重要的数据结构,LeetCode 中有很多...

    gasstationleetcode-LeetCode-:坚持每天刷一道算法题,冲鸭!!!

    gas station leetcode LeetCode- 坚持每天刷一道算法题,冲鸭!!! day1 验证回文字符串 day2 亲密字符串 柠檬水找零 day3 反转字符串中的单词 day4 三数之和 day5 数组中的第k个最大元素 day6 环形链表II day7 无...

    gasstationleetcode-leetcode:leetcode

    gas station leetcode 什么是LeetCode? 官网(中文): 官网(英文): LeetCode是一个在线算法编程网站,上面主要收集了各大IT公司的笔试面试题,对于找工作是一个不可多得的好帮手。 (Notes: Last updated table:...

    leetcode c++程序

    11. LeetCode题目案例:文档中提到了一些特定的LeetCode题目案例,如SetMatrixZeroes、GasStation、Candy、SingleNumber等。这些案例覆盖了数组、单链表、字符串等数据结构的多种操作,体现了各种算法应用场景。 12...

    gasstationleetcode-LeetCode:Leetcode问题解决方案

    在LeetCode平台上,题目“Gas Station”是一道著名的算法问题,属于中等难度。这个问题旨在测试程序员对于数组处理、线性搜索以及优化算法的理解。在这个压缩包文件"gasstationleetcode-LeetCode:LeetCode问题解决...

    gasstationleetcode-leetcode:我对leetcode问题的解决方案

    gas station leetcode leetcode # Title README Java Python 0002 0003 0005 0010 0011 0015 0019 0022 0023 0046 0050 0054 0064 0070 0079 0079 0084 0098 0102 0103 0104 README 0110 0110 0124 0125 0134 0142 ...

    gasstationleetcode-LeetCode:LeetCode算法题目解答

    gas station leetcode LeetCode算法高频题目汇总 序号 题目 1 2 3 4 5 7 8 9 11 12 13 14 15 16 17 19 20 21 22 23 24 25 26 27 28 31 32 33 34 35 38 39 40 41 42 43 45 46 47 48 49 50 53 54 55 56 59 62 64 67 69...

    leetcode-cpp刷题

    - **2.1.21 Gas Station** - 汽油站问题,找到可以从头到尾循环的起始站点。 - 实现思路:累积差值法。 - **2.1.22 Candy** - 分发糖果问题,确保相邻的孩子获得的糖果数量不同。 - 实现思路:动态规划,先从...

Global site tag (gtag.js) - Google Analytics