摘要:这样我们开始遍历数组,如果是负数,说明开出该加油站后无法到达下一个加油站,这样旅程的起点更新为下一个加油站。
Gas Station
贪心法 复杂度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.
时间 O(N) 空间 O(K)
思路我们把将gas中每个值都减去cost中对应的值,这样gas就成为了开出该加油站到下一个加油站时,该加油站加的油用剩到多少。这样我们用一个tank变量记录汽车每开到一个加油站后油箱里累计剩下多少油,每到一个加油站就更新。这样我们开始遍历gas数组,如果tank是负数,说明开出该加油站后无法到达下一个加油站,这样旅程的起点更新为下一个加油站。因为旅程是环状的我们遍历的加油站数组应为2*gas.length-1,这样能保证我们以最后一个加油站为起点时也能继续验证。
代码public class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { // gas减去cost,得到净油值 for(int i = 0; i < cost.length; i++){ gas[i] -= cost[i]; } int tank = 0, res = -1; for(int i = 0; i < gas.length * 2 - 1; i++){ int idx = i % gas.length; // 更新油箱 tank += gas[idx]; // 如果油箱为负,说明走不到下一个加油站 if(tank < 0){ res = idx + 1; tank = 0; } } // 如果起点在最后一个加油站之后,说明无解 return res >= gas.length ? -1 : res; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/64649.html
摘要:看到这个题目,怎样可以不把它当成一个环路来分析,以及减少多余的空间呢例如,我们引入单次剩余油量,剩余油量和,总剩余油量和,以及可行起点四个参数。大体上说,只要,一定有解。所以跳过这个耗油量很大的油站,然后将下一个油站作为起点继续判断即可。 Problem There are N gas stations along a circular route, where the amount ...
摘要:先实现栈操作遍历链表,把每个节点都进中然后再遍历链表,同时节点依次出栈,二者进行比较。 ?作者简介:大家好,我是车神哥,府学路18号的车神? ?个人主页:应无...
摘要:关于递归这里提一两点递归基本有这几步递归的模板,终止条件,递归调用,逻辑处理。 ?作者简介:大家好,我是车神哥,府学路18号的车神? ?个人主页:应无所住而生...
摘要:有效二叉搜索树定义如下节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。而我们二叉搜索树保证了左子树的节点的值均小于根节点的值,根节点的值均小于右子树的值,因此中序遍历以后得到的序列一定是升序序列。 ...
阅读 1516·2021-11-16 11:44
阅读 7322·2021-09-22 15:00
阅读 4394·2021-09-02 10:20
阅读 1877·2021-08-27 16:20
阅读 2332·2019-08-26 14:00
阅读 2886·2019-08-26 11:44
阅读 1588·2019-08-23 18:33
阅读 1829·2019-08-22 17:28