贪心---加油站 Posted on 2021-08-12 00:00:00 2021-08-12 00:00:00 by Author 摘要 有一场汽车比赛,需要经过N个站点,每个站点都标注了本站能够加的油量与到达下一个站点消耗的油量,你能从N个站点选择一个起点位置,保证每一辆车都能完整跑一圈吗。 # 贪心---加油站 1. 题目描述 在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发,开始时油箱为空。如果你可以绕环路行驶一周,则返回出发时加油站的编号,否则返回 -1。 **提示:** 如果题目有解,该答案即为唯一答案。 输入数组均为非空数组,且长度相同。 输入数组中的元素均为非负数。 2. 示例描述 - 示例一 ```java 输入: 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 可为起始索引。 ``` - 示例二 ```java 输入: 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 升汽油。 因此,无论怎样,你都不可能绕环路行驶一周。 ``` 3. 解题思路 - 对于本题来说,可以拿暴力算法进行解决,就是加油站每个位置都当作起始点跑一遍,如果有一个站点可以跑完整圈,那么就找到了起始点了,如果所有加油点都跑不完一圈,那么就没有一个符合作为起始点的加油站,对于暴力解法来说总体时间复杂度为O(N^2),比较容易实现。 - 其实这道题可以这样想,首先可以计算总体跑下来剩余的油量,如果一圈下来剩余的油量为负数,那么不管从哪个位置跑都不能完整跑一圈。为什么尼,因为我们可以这样想,跑下来油量为负数,说明某个加油站可以加的油远远小于达到下个站点需要的油量,尽管之前车里还剩油量,那么在本加油站加了油后,也不能满足到达下一个加油站消耗的油量,要不然,它最后的油量也不可能为负数啊,这里可以仔细想想哦。 - 如果总体跑一圈下来,剩余油量刚好为零,或者还有剩余的油量,那么说明必定有某个站点可以加的油量远远大于它到下个站点需要的油量,尽管之后的站点可以加的油量少于需要消耗的量,在本站点就可以保留到之后站点使用,要不然跑一圈下来油量也不可能为正数啊,这里也可以好好想想呀。 - 那么这样想其实一趟循环就可以完事了,如果可以完整跑一圈下来,那么其中思想可以这样想,每到一个站点,我们判断到达下个站点剩余的油量是否为负数,如果 为负数,那么之前的起点位置就不能使汽车跑完一圈,那么起点位置换为下一个站点。那么等循环结束,就可以找到起点位置了(前提是可以完整跑完一圈的情况哦)。 - 具体实现逻辑如下代码,这里用的也是贪心思想哦,可以好好品味一下。 4. 代码示例 ```java int canCompleteCircuit(int[] gas, int[] cost) { //当前还剩的油量 int currentSum = 0; //跑一圈下来剩余的油量 int totalSum = 0; for (int i = 0; i < cost.length; i++) { //每到一个加油站加满油量与到达下一个加油站消耗油量的差 totalSum += gas[i] - cost[i]; } //如果跑一圈下来剩余油量为负数,那么不管从哪个位置跑都不能完整跑一圈 if (totalSum < 0) return -1; //如果跑一圈下来油量还剩余或者刚好为0时,说明可以跑一圈。 int startIndex = 0; for (int i = 0; i < cost.length; i++) { //计算到达此位置时还有的油量 currentSum += gas[i] - cost[i]; //如果在此位置剩余油量为负,说明从之前开始位置开始是不能完整跑一圈 if (currentSum < 0) { //那么开始从下个位置开始尝试 startIndex = i + 1; currentSum = 0; } } //前提我们已经知道,是可以完整跑一圈,所以跑完整个加油站,油量一直为正数,那么说明开始位置就找到了。 return startIndex; } ```
{{ item.content }}
{{ child.content }}