广州市住房城乡建设部门户网站,启航做网站好吗,免费模板建站网站,外包服务平台题目#xff1a;
链接#xff1a;LeetCode 134. 加油站 难度#xff1a;中等
在一条环路上有 n 个加油站#xff0c;其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车#xff0c;从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中…题目
链接LeetCode 134. 加油站 难度中等
在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。
给定两个整数数组 gas 和 cost 如果你可以绕环路行驶一周则返回出发时加油站的编号否则返回 -1 。如果存在解则 保证 它是 唯一 的。
示例 1: 输入: gas [1,2,3,4,5], cost [3,4,5,1,2] 输出: 3 解释: 从 3 号加油站(索引为 3 处)出发可获得 4 升汽油。此时油箱有 0 4 4 升汽油 开往 4 号加油站此时油箱有 4 - 1 5 8 升汽油 开往 0 号加油站此时油箱有 8 - 2 1 7 升汽油 开往 1 号加油站此时油箱有 7 - 3 2 6 升汽油 开往 2 号加油站此时油箱有 6 - 4 3 5 升汽油 开往 3 号加油站你需要消耗 5 升汽油正好足够你返回到 3 号加油站。 因此3 可为起始索引。 示例 2: 输入: gas [2,3,4], cost [3,4,3] 输出: -1 解释: 你不能从 0 号或 1 号加油站出发因为没有足够的汽油可以让你行驶到下一个加油站。 我们从 2 号加油站出发可以获得 4 升汽油。 此时油箱有 0 4 4 升汽油 开往 0 号加油站此时油箱有 4 - 3 2 3 升汽油 开往 1 号加油站此时油箱有 3 - 3 3 3 升汽油 你无法返回 2 号加油站因为返程需要消耗 4 升汽油但是你的油箱只有 3 升汽油。 因此无论怎样你都不可能绕环路行驶一周。 提示:
gas.length ncost.length n1 n 1050 gas[i], cost[i] 104
方法一
函数图像法 sum 代表路途中油箱的油量如果把这个「最低点」作为起点即把这个点作为坐标轴原点就相当于把图像「最大限度」向上平移了 如果经过平移后图像全部在 x 轴以上就说明可以行使一周。
代码一
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int n gas.size();int minsum 0, minpos 0; //函数最低点的值函数最低点的坐标出发站编号int sum 0;for(int i 0; i n; i){sum gas[i] - cost[i];if(sum minsum) {minsum sum;minpos i 1;}}if(sum 0) return -1;return minpos % n;}
};时间复杂度O(n)空间复杂度O(1)。
方法二
贪心解法
用贪心思路解决这道题的关键在于以下这个结论
如果选择站点i作为起点「恰好」无法走到站点j那么i和j中间的任意站点k都不可能作为起点。
比如说如果从站点1出发走到站点5时油箱中的油量「恰好」减到了负数那么说明站点1「恰好」无法到达站点5那么你从站点2,3,4任意一个站点出发都无法到达5因为到达站点5时油箱的油量也必然被减到负数。
如何证明这个结论
假设sum记录当前油箱中的油量如果从站点i出发sum 0走到j时恰好出现sum 0的情况那说明走到i, j之间的任意站点k时都满足sum 0对吧。
如果把k作为起点的话相当于在站点k时sum 0那走到j时必然有sum 0也就是说k肯定不能是起点。
拜托从i出发走到k好歹sum 0都无法达到j现在你还让sum 0了那更不可能走到j了对吧。
综上这个结论就被证明了。
回想一下我们开头说的暴力解法是怎么做的
如果我发现从i出发无法走到j那么显然i不可能是起点。
现在我们发现了一个新规律可以推导出什么
如果我发现从i出发无法走到j那么i以及i, j之间的所有站点都不可能作为起点。
看到冗余计算了吗看到优化的点了吗
这就是贪心思路的本质如果找不到重复计算那就通过问题中一些隐藏较深的规律来减少冗余计算。
代码二
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int n gas.size();for(int i 0; i n;){int sum 0;bool flag true; //以i为出发站时能否环行一周for(int j i; j i n; j){sum gas[j % n] - cost[j % n]; //行至第j1个加油站时油箱内的油量if(sum 0) {if(j 1 n) return -1; //全部出发点已遍历完未找到可行解i (j 1) % n; //无法从第i站到第j1站则从中间任意一站都无法到第j1站。那么以第j1站为出发站继续检查flag false;break;}}if(flag) return i; //以第i站为出发站可以走完一周返回i}return -1;}
};时间复杂度O(n)空间复杂度O(1)。
