贪心算法（一）

谁借莪１个温暖的怀抱￠ 2023-09-30 11:45 16阅读 0赞

#### 文章目录 ####

*  贪心算法简介
 *  LeetCode 45跳跃游戏
 *  LeetCode 55跳跃游戏 ||
 *   *

记录一些自己学到的知识，同时希望能帮到各位小伙伴们学习一些东西，如果有什么写的不好的地方或者需要更改的，还请大佬指正

## 贪心算法简介 ##

贪心算法(又称贪婪算法)是指：在每一步求解的步骤中，它要求“贪婪”的选择最佳操作，并希望通过一系列的最优选择，能够产生一个问题的（全局的）最优解。

贪心算法每一步必须满足一下条件：

1、可行的：即它必须满足问题的约束。

2、局部最优：他是当前步骤中所有可行选择中最佳的局部选择。

3、不可取消：即选择一旦做出，在算法的后面步骤就不可改变了。

> 因此，贪心算法说白了就是在子问题的每一步中取最优解，然后把每一步的最优解合成原来问题的解，虽然最终答案可能不是最优的，但与最中答案很接近。  
> 以下是关于贪心算法的几道题，可以参考着学习一下

## LeetCode 45跳跃游戏 ##

问题

> 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。  
> 数组中的每个元素代表你在该位置可以跳跃的最大长度。  
> 判断你是否能够到达最后一个下标。

示例1

> 输入：nums = \[2,3,1,1,4\]  
> 输出：true  
> 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例2

> 输入：nums = \[3,2,1,0,4\]  
> 输出：false  
> 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

思路:  
对于这种题型，就用到了贪心的思想。比如在示例1中，刚开始nums\[0\]的值为2，可以跳两步，可以调到nums\[1\]值为3的位置，也可以跳到nums\[2\]值1的地方，我们会选择让其跳到下标为1的地方，因为跳到此处下标值更大，跳的更远，我们只需考虑每次能跳到的最远下标即可，因此最后所需的步也可能就最少。那么怎么判定达到终点呢?  
最初位置下标为0，而此时nums\[0\]为2，也就是说能跳到下标为2的位置结束，当跳到下标为1时，可以跳三步到达终点，所以我们是通过数组下标i+nums\[i\]来计算其能跳到的位置的。  
因此我们的代码如下:

class Solution {
        
        public boolean canJump(int[] nums) {
        
            if(nums.length==1) return true;
            int coverage=nums[0] //这里i=0，所以初始化的时候加不加i无所谓，coverage表示开始跳时能到达的下标；
            for(int i=0;i<=coverage;i++){
        
                coverage=Math.max(coverage,i+nums[i]);//这里如果遇到能够达到更大的下标的情况，就更新coverage的值；
                if(coverage>=nums.length-1) return true;//如果if成立，则说明能跳到最后的位置，因此返回TRUE;
                }
                return false;//如果i大于了coverage还没有跳到最后位置(退出循环了)，则跳不到最后
            }
    }

因此本题就解决了。

## LeetCode 55跳跃游戏 || ##

来让我们看下一道题。  
问题

> 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。  
> 数组中的每个元素代表你在该位置可以跳跃的最大长度。  
> 你的目标是使用最少的跳跃次数到达数组的最后一个位置。  
> 假设你总是可以到达数组的最后一个位置。

示例1

> 输入: nums = \[2,3,1,1,4\]  
> 输出: 2  
> 解释: 跳到最后一个位置的最小跳跃数是 2。  
> 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例2

> 输入: nums = \[2,3,0,1,4\]  
> 输出: 2

分析:  
首先这道题是对跳跃游戏 | 的延伸，只不过|是让我们求能不能到跳到最后，而这个是让我们求最少需要几步到达最后一个位置，同样也用到了贪心的思想。

class Solution {
        
        public int jump(int[] nums) {
        
        if(nums.length==1||nums.length==0) return 0;
        int count=0; //记录最少到达最后所要走的步数
        int temp=nums[0]; //和第一道一样，初始化所能到达的位置
        int cur=temp;//定义这个cur是如果i到达temp时，将cur赋值给temp，cur保存了从i到temp所能达到的最大下标
        for(int i=0;i<=temp;i++){
        
        if(temp>=nums.length-1) return count+1; //返回count+1的原因是因为我们定义的count初始值为0，如果条件成立了，需要再走一步才能到达终点。
        cur=cur<=i+nums[i]?i+nums[i]:cur;
        if(i==temp){
        
         temp=cur;
         count++;
        }//此时i已经到达了temp的第一个区间，需要temp更新下一个更大的区间
            }   
        return count;
        }
    }

这道题到这里也就结束了，||和|的区别在于第二题是当  
i到达第一个区间再更新区间，因为如果nums\[0\]=2,而nums\[1\]=4,nums\[2\]=6时，显然要到下标为2再跳，因此用cur保存最大值，将nums\[2\]+2赋值给temp。

本文到这里就先结束了，还会记录其他的题以及题型，如果有什么写的不对的地方，还希望各位大佬看到后指正。

###  ###