盱眙建设局网站,可以做投票功能的网站,110建筑人才网官网,措美网站建设上一篇博客算法整理——【贪心算法简述】-CSDN博客#xff0c;我们介绍了贪心算法的基础知识#xff0c;现在我们要对此进行进一步练习。
一、跳跃游戏II
例题为45. 跳跃游戏 II - 力扣#xff08;LeetCode#xff09;#xff0c;给定一个长度为 n 的 0 索引整数数组 nu…上一篇博客算法整理——【贪心算法简述】-CSDN博客我们介绍了贪心算法的基础知识现在我们要对此进行进一步练习。
一、跳跃游戏II
例题为45. 跳跃游戏 II - 力扣LeetCode给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
最理想的情况是每一步尽可能往远跳这样尽快跳到最后。但是我们不能单纯的取最远的点因为会存在[2,3,1,1,4]这样的例子如果在位置0跳到最远位置2则会需要三步才能到终点。
我们需要引入覆盖范围的思想覆盖范围是指我们能跳到达的区域都属于覆盖范围不是具体的某个终点。比如我们可以计算第一次跳跃的覆盖范围、第二次的覆盖范围等等主要是记录当前步数的覆盖范围的最大值最终看什么时候终点被包括。基于此我们现在的贪心思路变成了每一步尽可能扩大我们的覆盖范围。
代码如下
class Solution {
public:int jump(vectorint nums) {int ret 0;//记录步数int cur 0;//记录当前步数最大的覆盖范围int next 0;//记录下一步可到达的最大覆盖范围if(nums.size() 1) return 0;for(int i 0; inums.size(); i){next max(next, inums[i]);if(i cur){ret;if(nextnums.size()-1) return ret;cur next;}}return ret;}
};
二、加油站
例题为134. 加油站 - 力扣LeetCode在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。给定两个整数数组 gas 和 cost 如果你可以按顺序绕环路行驶一周则返回出发时加油站的编号否则返回 -1 。如果存在解则保证它是唯一的。
首先我们可以通过将每点的gas-cost得到经过该加油站后油量的净增加或减少的量dif[i]。如果对所有点的净增加减少进行累加最后结果如果为负则说明无论从哪一点开始都不能够跑完一圈此时需要返回-1。如果为正则需要找到那个起始点。
本题的解题重点为以下的一句思路我们从0开始累加dif[i]和记为sum一旦sum小于零说明i之前的都不能作为起始位置具体证明可以自己思考。于是我们需要从i1开始累加和遍历。本题的局部最优为当前累加dif[i]的和sum一旦小于0起始位置至少要是i1。全局最优为找到可以跑一圈的起始位置。
整体代码如下
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {vectorint dif(gas.size());int sum 0;for(int i 0; igas.size(); i){dif[i] gas[i]-cost[i];sumdif[i];//累计总油量减去总消耗}if(sum0)//从任何一个点都不可能跑完一圈{return -1;}sum 0;int ret 0;for(int i 0;igas.size(); i){sumdif[i];if(sum0){ret i1;sum 0; }}return ret;}
};
说明本文为作者整理知识点用于复习巩固参考了代码随想录的讲解有问题可以联系作者欢迎讨论~
