算法整理——【贪心算法练习（1）】

上一篇博客算法整理——【贪心算法简述】-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(vector<int>& nums) {int ret = 0;//记录步数int cur = 0;//记录当前步数最大的覆盖范围int next = 0;//记录下一步可到达的最大覆盖范围if(nums.size() == 1) return 0;for(int i = 0; i<nums.size(); i++){next = max(next, i+nums[i]);if(i == cur){ret++;if(next>=nums.size()-1) return ret;cur = next;}}return ret;}
};

二、加油站

例题为134. 加油站 - 力扣（LeetCode），在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯一的。

首先我们可以通过将每点的gas-cost，得到经过该加油站后油量的净增加（或减少）的量dif[i]。如果对所有点的净增加（减少）进行累加，最后结果如果为负，则说明无论从哪一点开始都不能够跑完一圈，此时需要返回-1。如果为正，则需要找到那个起始点。

本题的解题重点为以下的一句思路：我们从0开始累加dif[i]，和记为sum，一旦sum小于零，说明i之前的都不能作为起始位置（具体证明可以自己思考）。于是我们需要从i+1开始累加和遍历。本题的局部最优为当前累加dif[i]的和sum一旦小于0，起始位置至少要是i+1。全局最优为找到可以跑一圈的起始位置。

整体代码如下：

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {vector<int> dif(gas.size());int sum = 0;for(int i = 0; i<gas.size(); i++){dif[i] = gas[i]-cost[i];sum+=dif[i];//累计总油量减去总消耗}if(sum<0)//从任何一个点都不可能跑完一圈{return -1;}sum = 0;int ret = 0;for(int i= 0;i<gas.size(); i++){sum+=dif[i];if(sum<0){ret = i+1;sum = 0;   }}return ret;}
};

说明：本文为作者整理知识点用于复习巩固，参考了代码随想录的讲解，有问题可以联系作者欢迎讨论~