问题描述:
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.
原问题链接:https://leetcode.com/problems/gas-station/
问题分析
从问题描述里我们相对比较容易找到一个思路,就是因为这里是走一圈要求遍历整个数组。那么它们所有消耗的汽油以及加的汽油的差值就能确定我们最后能否完整的走一圈。至少通过这个条件我们就可以判断能否走完一圈。
现在剩下的就是要确定怎么找到那个可以走完一圈的点。假设我们从起点0开始,当它往前一直累加的某个点的时候,出现求和的值小于0了。我们该怎么选择呢?从这个累加和小于0的结果我们至少可以知道,只要绕这一圈,从起点到这个点的这一段的总和是小于0的。我们取当前点的后面一个位置才有可能找到累加和大于0的段。在实现的时候,我们取的当前节点的后一个可能超过节点n,那么这个时候需要进行取余操作。在最终我们取到的节点是否有效就取决于所有节点的累加和是否大于等于0。
详细的代码实现如下:
public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int n = gas.length; int curSum = 0, totalSum = 0, start = 0; for(int i = 0; i < n; i++) { curSum += gas[i] - cost[i]; totalSum += gas[i] - cost[i]; if(curSum < 0) { start = (i + 1) % n; curSum = 0; } } return totalSum >= 0 ? start : -1; } }
相关推荐
gas station leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9...
Leetcode\gas station(134)。 swift Leetcode\group anagrams(49).swift Leetcode\group 给定他们所属的组大小的人(1282).swift Leetcode\数组中的第k 个最大元素(215).swift Leetcode\最长递增子序列(300).swift ...
gas station leetcode 什么是LeetCode? 官网(中文): 官网(英文): LeetCode是一个在线算法编程网站,上面主要收集了各大IT公司的笔试面试题,对于找工作是一个不可多得的好帮手。 (Notes: Last updated table:...
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 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...
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 Rust Leetcode 练习使用Rust语言刷或者算法题目, 一些不支持Rust判题的会使用Python进行解决,并对解题思路进行简单分析,分类,及总结. Environment rustc 1.44.0 cargo 1.44.0 How to test ...
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 station leetcode LeetCode- 坚持每天刷一道算法题,冲鸭!!! day1 验证回文字符串 day2 亲密字符串 柠檬水找零 day3 反转字符串中的单词 day4 三数之和 day5 数组中的第k个最大元素 day6 环形链表II day7 无...
gas ...gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归 valid-palindrome 模拟 pascals-triangle 模拟 pasca
leetcode 加油站 实施:蛮力 O(N ^ 2) class Solution { public int canCompleteCircuit ( int [] gas , int [] cost ) { for ( int i = 0 ; i < gas . length; i ++ ) { int current_stop = i; int count = 0 ; ...
gas station leetcode Data_Structure 该文记录笔者刷的pat和leetcode的题解。 Pat甲级题解: 模拟: 链表: 树: 图: LeetCode题解:
gas station leetcode Leetcode solutions written in Javascript 分类标准 重点:必须掌握的题型。通常都有着代表一类题型的解法,或者可以举一反三。 提高:难度相对高的题,或者思路巧妙的题,提升自我的目的可以...
gas station leetcode 记录leetCode的解题思路 Arrays 发现力不从心的地方很多,我可能有很多的功课需要补足,所以这个专题暂时停止更新 更新剑指offer的解题 备注 1. 部分完工:可以实现,但算法待改进 2. 未完工:...
gas station leetcode algorithm 记录一下学习算法的一些代码。 冗余连接 II 全排列 II 左叶子之和 子集 把二叉搜索树转换为累加树 监控二叉树 合并二叉树 二叉搜索树中的众数 从中序与后序遍历序列构造二叉树 路径...
gas station leetcode LeetCodeCPP 题目来自于牛客网在线编程模块leetcode经典编程题, 激励自己进行算法练习。 148道LeetCode数据结构算法经典在线编程题C++、Java实现 、C++版本:
gas station leetcode 记录leetCode的解题思路 ##Arrays ####发现力不从心的地方很多,我可能有很多的功课需要补足,所以这个专题暂时停止更新