原题链接:http://oj.leetcode.com/problems/gas-station/这是一道具体问题的题目,brute force的方法比较容易想到,就是从每一个站开始,一直走一圈,累加过程中的净余的油量,看它是不是有出现负的,如果有则失败,从下一个站开始重新再走一圈;如果没有负的出现,则这个站可以作为起始点,成功。可以看出每次需要扫描一圈,对每个站都要做一次扫描,所以时间复杂度是O(n^2)。代码比较直接,这里就不列举了。接下来说说如何提高这个算法。方法主要思想是把这个圈划分成一个个的负序列,以及一个正序列(如果存在的话)。从任意一个站出发,我们可以累加油的净余量,如果出现负的,序列结束,开启一个新的,并且证明旧的这个序列的起点不能作为起点,因为会出现负油量,不能继续前进。下面我们证明不仅这个负序列的起点不能作为起点,负序列中的任意一点都不能作为起点。
证明:假设我们取定负序列中的一个站作为起点,因为一个序列一旦遇到负的净余量就会结束并且开启新的,那么说明在这个起点前的累加结果必然是正数(否则会结束这个序列,则前面不会是这个序列的一部分)。如此我们从当前序列出发必然会使走到序列终点时负的油量更大,本来已经是负的,所以不能去负序列的任意一个结点作为起点。根据上面的划分方式,我们会把圈分成一段段的序列,而且其中最多只有一个正序列,那就是绕一圈回到起点的那个序列(当然也有可能整个圈是一个正序列,就是油量一直为正,那么我们测的开始点就可以作为起点了)。接下来我们证明如果将全部油量累计起来,总是为正,那么一定能找到一个起点,使得可以走完一圈,也就是一定有解。
证明:按照我们之前的划分,整个圈会被划分成有累积量为s1,
s2, ..., sk 的负序列,以及一个正序列拥有油量sp(这里正序列一定存在因为全部累加和是正的,如果全是负序列那么结果不会是正的)。而且我们知道s1+s2+...+sk+sp>0,也就是说sp>-s1-s2-...-sk。换句话说,如果我们从sp对应的站的起点出发,在sp对应的序列会一直是正的,并且,当他走到负序列时,因为sp的正油量大于所有负油量的总和,所以累加油量会一直正,完整整个圈的行驶。这证明了只要累加油量是正的,一定能找到一个起点来完成任务。根据上面的两个命题,我们可以来实现代码,需要维护两个量,一个是总的累积油量total,另一个是当前序列的累计油量sum,如果出现负的,则切换起点,并且将sum置0。总共是需要扫描所有站一次,时间复杂度是O(n)。而只需要两个额外变量,空间复杂度是O(1)。代码如下:public int canCompleteCircuit(int[] gas, int[] cost) {
if(gas==null || gas.length==0 || cost==null || cost.length==0 || gas.length!=cost.length)
return -1;
int sum = 0;
int total = 0;
int pointer = -1;
for(int i=0;i<gas.length;i++)
{
int diff = gas[i]-cost[i];
sum += diff;
total += diff;
if(sum<0)
{
sum=0;
pointer=i;
}
}
return total>=0?pointer+1:-1;
}
这个题目的优化解法更像是一个数学题,需要定义数学模型并证明命题正确性,比较需要数学逻辑的功底。通过定义的模型以及证明的命题来做一部分贪心。
分享到:
相关推荐
gas ...gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归 valid-palindrome 模拟 pascals-triangle 模拟 pasca
gas station leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9...
LeetCode- 坚持每天刷一道算法题,冲鸭!!! day1 验证回文字符串 day2 亲密字符串 柠檬水找零 day3 反转字符串中的单词 day4 三数之和 day5 数组中的第k个最大元素 day6 环形链表II day7 无重复字符的最长子串 day...
这道题,题目名字就叫gas-station(网址的最后一部分),于是此题目的代码也在gas-station.c文件中。 当一道题通过测试且性能达到预期时,将在git中commit,注释为“测试通过,性能达标”。若commit的注释为其它内容...
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...
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 solutions written in Javascript 分类标准 重点:必须掌握的题型。通常都有着代表一类题型的解法,或者可以举一反三。 提高:难度相对高的题,或者思路巧妙的题,提升自我的目的可以...
gas station leetcode 什么是LeetCode? 官网(中文): 官网(英文): LeetCode是一个在线算法编程网站,上面主要收集了各大IT公司的笔试面试题,对于找工作是一个不可多得的好帮手。 (Notes: Last updated table:...
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 ...
Leetcode\gas station(134)。 swift Leetcode\group anagrams(49).swift Leetcode\group 给定他们所属的组大小的人(1282).swift Leetcode\数组中的第k 个最大元素(215).swift Leetcode\最长递增子序列(300).swift ...
gas station leetcode Rust Leetcode 练习使用Rust语言刷或者算法题目, 一些不支持Rust判题的会使用Python进行解决,并对解题思路进行简单分析,分类,及总结. Environment rustc 1.44.0 cargo 1.44.0 How to test ...
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 记录leetCode的解题思路 Arrays 发现力不从心的地方很多,我可能有很多的功课需要补足,所以这个专题暂时停止更新 更新剑指offer的解题 备注 1. 部分完工:可以实现,但算法待改进 2. 未完工:...
gas station leetcode algorithm 记录一下学习算法的一些代码。 冗余连接 II 全排列 II 左叶子之和 子集 把二叉搜索树转换为累加树 监控二叉树 合并二叉树 二叉搜索树中的众数 从中序与后序遍历序列构造二叉树 路径...
gas station leetcode Data_Structure 该文记录笔者刷的pat和leetcode的题解。 Pat甲级题解: 模拟: 链表: 树: 图: LeetCode题解:
gas station leetcode 记录leetCode的解题思路 ##Arrays ####发现力不从心的地方很多,我可能有很多的功课需要补足,所以这个专题暂时停止更新
gas station leetcode LeetCodeCPP 题目来自于牛客网在线编程模块leetcode经典编程题, 激励自己进行算法练习。 148道LeetCode数据结构算法经典在线编程题C++、Java实现 、C++版本: