首页 > 编程语言 >算法打卡day28|贪心算法篇02|Leetcode 122.买卖股票的最佳时机 II、55. 跳跃游戏、45.跳跃游戏 II

算法打卡day28|贪心算法篇02|Leetcode 122.买卖股票的最佳时机 II、55. 跳跃游戏、45.跳跃游戏 II

时间:2024-03-28 09:29:55浏览次数:38  
标签:int 步数 II 算法 跳跃 覆盖范围 贪心

算法题

Leetcode 122.买卖股票的最佳时机 II

题目链接:122.买卖股票的最佳时机 II

 大佬视频讲解:买卖股票的最佳时机 II视频讲解

 个人思路

因为只有一只股票,且两天作一个交易单元,那每次只收集正利润就可以最终最多可以获取的利润,可以用贪心。

解法
贪心法

从下图可以发现,其实收集每天的正利润就可以,收集正利润的区间,就是股票买卖的区间,而且只需要关注最终利润,不需要记录区间

局部最优:收集每天的正利润,全局最优:求得最大利润

class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;//最终利润

        for (int i = 1; i < prices.length; i++) {
            result += Math.max(prices[i] - prices[i - 1], 0);//只收集正利润
        }

        return result;
    }
}

时间复杂度:O(n);(遍历整个数组)

空间复杂度:O(1);(常量级的变量)


 Leetcode  55. 跳跃游戏

题目链接:55. 跳跃游戏

大佬视频讲解:跳跃游戏视频讲解

个人思路

可以每次取最大的跳跃步数,这个就是可以跳跃的覆盖范围,当覆盖范围盖过终点 就代表能跳到终点。每步取最优,最后推出全局最优,用贪心。

解法
贪心法

这个问题转化为跳跃覆盖范围究竟可不可以覆盖到终点!

每次移动取最大跳跃步数(得到最大的覆盖范围),每移动一个单位,就更新最大覆盖范围。

贪心算法局部最优解:每次取最大跳跃步数(取最大覆盖范围),整体最优解:最后得到整体最大覆盖范围,看是否能到终点

i 每次移动只能在 cover 的范围内移动,每移动一个元素,cover 得到该元素数值(新的覆盖范围)的补充,让 i 继续移动下去。而 cover 每次只取 max;如果 cover 大于等于了终点下标,直接 return true 。

class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        int coverRange = 0; //覆盖范围, 初始覆盖范围应该是0,因为下面的迭代是从下标0开始的

        //在覆盖范围内更新最大的覆盖范围
        for (int i = 0; i <= coverRange; i++) {
            coverRange = Math.max(coverRange, i + nums[i]);

            if (coverRange >= nums.length - 1) {//找到覆盖终点
                return true;
            }
        }
        return false;
    }
}

时间复杂度:O(n);(遍历整个数组)

空间复杂度:O(1);(常量级的变量)


 Leetcode  45.跳跃游戏 II

题目链接:45.跳跃游戏 II

大佬视频讲解:跳跃游戏 II视频讲解

 个人思路

这道题和上一题思路类似;只是本题要计算最少步数。在计算时,当前可移动距离尽可能多走,如果还没到终点,步数再加一。一步尽可能多走,从而达到最少步数。局部可以推全局,用贪心。

解法
贪心法

在解题时要注意,不能真的能跳多远就跳多远,那样就不知道下一步最远能跳到哪里了。

要从覆盖范围出发,不管怎么跳,覆盖范围内一定是可以跳到的,以最小的步数增加覆盖范围,覆盖范围一旦覆盖了终点,得到的就是最少步数.

所以这里需要统计两个覆盖范围,当前这一步的最大覆盖和下一步最大覆盖

如果移动下标达到了当前这一步的最大覆盖最远距离了,还没有到终点的话,那么就必须再走一步来增加覆盖范围,直到覆盖范围覆盖了终点.

class Solution {

    public int jump(int[] nums) {
        int result = 0;//步数
        
        int end = 0;// 当前覆盖的最远距离下标
        int temp = 0;// 下一步覆盖的最远距离下标

        //移动下标i只要遇到当前覆盖最远距离的下标,直接步数加一
        for (int i = 0; i <= end && end < nums.length - 1; ++i) {
            temp = Math.max(temp, i + nums[i]);//更新最大覆盖范围
            
            if (i == end) {// 可达位置的改变次数就是跳跃次数
                end = temp;
                result++;
            }
        }
        return result;
    }
}

时间复杂度:O(n);(遍历整个数组)

空间复杂度:O(1);(常量级变量)


 以上是个人的思考反思与总结,若只想根据系列题刷,参考卡哥的网址代码随想录算法官网

标签:int,步数,II,算法,跳跃,覆盖范围,贪心
From: https://blog.csdn.net/unstoppableyi/article/details/137019296

相关文章

  • SDC可伸缩的高维约束基准和算法
    可伸缩的高维约束基准和算法​ 在过去二十年里,进化约束多目标优化受到了广泛的关注和研究,并且已经提出了一些基准测试约束多目标进化算法(CMOEAs)。特别地,约束函数与目标函数值有紧密的联系,这使得约束特征太单调并且与真实世界的问题不同。因此,之前的CMOEAs不能特别好的解决现实......
  • 常用排序算法
    本博客将讲述常见的几种排序算法在日常码代码时,常常会用到排序,排序算法又有很多,每种排序都会有自己的特点和适用情况,我在这将总结几种排序算法,废话少说,开始!冒泡排序(bubblesort)冒泡排序,因像水泡一样一个接一个地冒出水面(排序),而得名。冒泡排序的思想是每次将最大的一次一次......
  • 高斯混合模型(GMM)和EM算法 —— python实现
    一、EM算法EM算法是一种迭代算法,用于含有隐含变量的概率模型参数的极大似然估计。设Y为观测随机变量的数据,Z为隐藏的随机变量数据,Y和Z一起称为完全数据。观测数据的似然函数为:模型参数θ的极大似然估计为:这个问题只有通过迭代求解,下面给出EM算法的迭代求解过程:step1、选择......
  • Floyd算法 【多源最短路】模板
    B3647【模板】Floyd-洛谷|计算机科学教育新生态(luogu.com.cn)#include<bits/stdc++.h>usingnamespacestd;constintN=1e2+10;constintinf=0x3f3f3f;intn,m;intg[N][N];voidfloyd(){for(intk=1;k<=n;k++){for(inti=1;i<=n;i++)......
  • R语言K-Means(K均值聚类)和层次聚类算法对微博用户特征数据研究
    全文链接:https://tecdat.cn/?p=32955原文出处:拓端数据部落公众号本文就将采用K-means算法和层次聚类对基于用户特征的微博数据帮助客户进行聚类分析。首先对聚类分析作系统介绍。其次对聚类算法进行文献回顾,对其概况、基本思想、算法进行详细介绍,再是通过一个仿真实验具体来强化......
  • 【面试精讲】Java垃圾回收算法分析和代码示例
    【面试精讲】Java垃圾回收算法分析和代码示例目录一、引用计数(ReferenceCounting)算法二、可达性分析(ReachabilityAnalysis)算法三、标记-清除(Mark-Sweep)算法四、复制(Copying)算法五、标记-整理(Mark-Compact)算法六、分代收集(GenerationalCollection)算法七、死亡对象判......
  • 08天【代码随想录算法训练营34期】第四章 字符串part01(● 344.反转字符串 ● 541. 反
    **344.反转字符串**classSolution:defreverseString(self,s:List[str])->None:left=0right=len(s)-1whileleft<right:temp=s[left]s[left]=s[right]s[right]=temp......
  • KMP算法
    ​ 应用于字符串匹配,主要思想就是当出现字符串不匹配时,可以知道一部分之前已经匹配的文本内容,利用这些信息避免从头再做匹配。如何利用已经匹配的文本内容?前缀表前缀表:用来回退,记录模式串与主串(文本串)不匹配的时候,模式串应该从哪里开始重新匹配。记录下标i之前(包括i)的字符串......
  • ADAS多传感器后融合算法解析-上篇
    ADAS多传感器后融合算法解析-上篇附赠自动驾驶学习资料和量产经验:链接ADAS系统是一种高自动化的软件应用,对系统的鲁棒性与可靠性要求很高,单一传感器往往存在一定限制,此时便需要多传感器融合。多传感器融合会带来如下收益:可以在部分场景提升整体感知精度。某一传感器出现......
  • ADAS多传感器后融合算法解析-下篇
    ADAS多传感器后融合算法解析-下篇在ADAS多传感器后融合(上)中我们介绍了后融合的接口、策略。本文将主要介绍后融合的实现流程、难点及注意事项。附赠自动驾驶学习资料和量产经验:链接二、后融合处理流程如下图为基本RC后融合系统流程图,接下来将介绍各个模块:如下图为Apollo......