134. 加油站
贪心思想: 因为本题用到了贪心算法所以先来了解一下「贪心算法」的问题需要满足的条件:
- 最优子结构:规模较大的问题的解由规模较小的子问题的解组成,规模较大的问题的解只由其中一个规模较小的子问题的解决定;
- 无后效性:后面阶段的求解不会修改前面阶段已经计算好的结果;
- 贪心选择性质:从局部最优解可以得到全局最优解。
综上可得:贪心算法就是做出当前状态下的最优选择认为就可以解决问题。
在本题中,要找到一个位置能够绕行一周回来。
“假设从x加油站出发经过z加油站最远能到达y加油站,那么从z加油站直接出发,不可能到达y下一个加油站。因为从x出发到z加油站时肯定 有存储的油 或者 到z的时候油已经没了,加上z加油站能够加上的油,这都到不了y的下一站。而直接从z出发刚开始是没有存储的油的,所以更不可能到达y的下一站。”文章来源:https://www.toymoban.com/news/detail-663531.html
也就是说,我们首先检查第 0 个加油站,并试图判断能否环绕一周;如果不能,就从第一个无法到达的加油站开始继续检查。文章来源地址https://www.toymoban.com/news/detail-663531.html
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int length = gas.length;
int index = 0;
// 这里不用for循环是因为,我们会使用跳过一些下标。所以,使用while是最好的
// 从头到尾遍历每个加油站,并且检查以该加油站为起点,能否行驶一周
while (index < length) {
// 当前index加油站的总汽油
int sumOfGas = 0;
// 当前index加油站的总花费汽油
int sumOfCost = 0;
// 当前index加油站最远能够走的最远步数
int count = 0;
// 判断从当前index下标出发能否环形一周
while (count < length) {
// 当前index加油站组成环形加油站
// 环形加油站下标
int currentIndex = (index + count) % length;
sumOfCost += cost[currentIndex];
sumOfGas += gas[currentIndex];
// 如果这个环形下标站点发现油不够了
if (sumOfCost > sumOfGas) {
// 当前index加油站组成环形加油站肯定是不满足题意的,跳出循环
break;
}
// 最远的步数+1
count++;
}
// 当前index能够环形一周
if (count == length) {
// 返回
return index;
} else {
// 就从无法到达的加油站开始继续检查。
index = index + count + 1;
}
}
// 所有加油站作为起点都不满足
return -1;
}
}
到了这里,关于【LeetCode】134. 加油站 - 贪心算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!