贪心算法(一)

2022年05月12日 阅读数:5
这篇文章主要向大家介绍贪心算法(一),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。


记录一些本身学到的知识,同时但愿能帮到各位小伙伴们学习一些东西,若是有什么写的很差的地方或者须要更改的,还请大佬指正

贪心算法简介

贪心算法(又称贪婪算法)是指:在每一步求解的步骤中,它要求“贪婪”的选择最佳操做,并但愿经过一系列的最优选择,可以产生一个问题的(全局的)最优解。java

贪心算法每一步必须知足一下条件:web

一、可行的:即它必须知足问题的约束。算法

二、局部最优:他是当前步骤中全部可行选择中最佳的局部选择。数组

三、不可取消:即选择一旦作出,在算法的后面步骤就不可改变了。svg

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

LeetCode 45跳跃游戏

问题spa

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

示例1xml

输入:nums = [2,3,1,1,4]
输出:true
解释:能够先跳 1 步,从下标 0 到达下标 1, 而后再从下标 1 跳 3 步到达最后一个下标。token

示例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。

本文到这里就先结束了,还会记录其余的题以及题型,若是有什么写的不对的地方,还但愿各位大佬看到后指正。