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 java_leetcode题解之Gas Station.java
python python_leetcode题解之134_Gas_Station
javascript js_leetcode题解之134-gas-station.js
gas station leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9...
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...
这道题,题目名字就叫gas-station(网址的最后一部分),于是此题目的代码也在gas-station.c文件中。 当一道题通过测试且性能达到预期时,将在git中commit,注释为“测试通过,性能达标”。若commit的注释为其它内容...
gas ...gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归 valid-palindrome 模拟 pascals-triangle 模拟 pasca
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/...
- **Gas Station**:寻找最短的加油路线。 - **Candy**:分糖果,确保每个孩子至少得到一块糖,尽可能公平。 - **Word Break**:判断一个字符串是否可以拆分为一个词汇表中的单词序列。 7. **链表(Linked List...
Leetcode\gas station(134)。 swift Leetcode\group anagrams(49).swift Leetcode\group 给定他们所属的组大小的人(1282).swift Leetcode\数组中的第k 个最大元素(215).swift Leetcode\最长递增子序列(300).swift ...
* Gas Station:给定一个数组,返回可以到达的加油站数量。这个题目需要使用贪心算法的思想,将数组分解成更小的子数组,并统计可以到达的加油站数量。 7. 链表 链表是一种非常重要的数据结构,LeetCode 中有很多...
gas station leetcode LeetCode- 坚持每天刷一道算法题,冲鸭!!! day1 验证回文字符串 day2 亲密字符串 柠檬水找零 day3 反转字符串中的单词 day4 三数之和 day5 数组中的第k个最大元素 day6 环形链表II day7 无...
gas station leetcode 什么是LeetCode? 官网(中文): 官网(英文): LeetCode是一个在线算法编程网站,上面主要收集了各大IT公司的笔试面试题,对于找工作是一个不可多得的好帮手。 (Notes: Last updated table:...
11. LeetCode题目案例:文档中提到了一些特定的LeetCode题目案例,如SetMatrixZeroes、GasStation、Candy、SingleNumber等。这些案例覆盖了数组、单链表、字符串等数据结构的多种操作,体现了各种算法应用场景。 12...
在LeetCode平台上,题目“Gas Station”是一道著名的算法问题,属于中等难度。这个问题旨在测试程序员对于数组处理、线性搜索以及优化算法的理解。在这个压缩包文件"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 ...
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...
- **2.1.21 Gas Station** - 汽油站问题,找到可以从头到尾循环的起始站点。 - 实现思路:累积差值法。 - **2.1.22 Candy** - 分发糖果问题,确保相邻的孩子获得的糖果数量不同。 - 实现思路:动态规划,先从...