代码随想录算法训练营第三十二天 | LeetCode 122. 买卖股票的最佳时机 II、55. 跳跃游戏、45. 跳跃游戏 II

简介: 代码随想录算法训练营第三十二天 | LeetCode 122. 买卖股票的最佳时机 II、55. 跳跃游戏、45. 跳跃游戏 II

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

1.1 思路

  1. 本题可以用贪心算法和动态规划解决。这里用贪心算法。本题中你买和卖分别是什么时候?多低时候买算低,多高时候卖算高?这些都不好把握,因此这思路不太好找。
  2. 以 prices 数组 [7,1,5,10,3,6,4] 为例,以 p[3]-p[0] 为例,是不是相当于 p3-p2+p2-p1+p1-p0。这一段区间就是相当于我每天的利润和,每天的利润有正有负,而只有正利润相加才对总利润有正向的作用,因此每天的利润就收集正的即可,以 prices 数组为例的利润数组 [-6,4,5,-7,3,-2] 这就是每天的利润组成的数组,这里只收集 4、5、3 就是我们的最大总利润,其实这里的 4、5 就相当于在 p1 买入 p3 卖出得到的利润,3 就相当于在 p4 买入 p5 卖出得到的利润。但此题不需要记录位置,只关注最大总利润
  3. 局部最优:只收集每天的正利润
  4. 全局最优:收集到的最大总利润。这样的思路找不出明显反例反驳
  5. 定义 result 收集每天的正利润,for(int i=1; i<price.length; i++),i 为什么从 1 开始,我们收集每天的利润是不是起码要从下标 1 的位置才能减去昨天的价格得出当天的利润对吧。然后 result+=Math.max(price[i]-price[i-1],0)。这样就是加上每天的正利润

1.2 代码

//
// 贪心思路
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;
    }
}

2. LeetCode 55. 跳跃游戏

2.1 思路

  1. 根据题目的 nums 数组我们可以知道在当前位置可以往前跳几步,但比如这个位置数字是 3 的话我是跳 1 步 还是 2 步 还是 3 步呢?跳到下一个元素了又应该跳几步呢?按照这个思路想就很难解出出来了。
  2. 我们可以换一个思路:我们不去纠结具体跳几步,只去看覆盖范围,如果在当前位置的覆盖范围能把终点覆盖了就是对了
  3. 局部最优:每次跳跃取最大跳跃步数(取最大覆盖范围)
  4. 全局最优:最后得到整体的最大覆盖范围,看是否能到终点
  5. 定义个 cover=0。如果数组长度就是 1 就是一定可以跳跃到的,因为最开始起始位置已经站在那了。 for(int i=0; i<=cover; i++),注意这里是<=cover,因为我们遍历是在覆盖范围内遍历的,然后得到可跳跃的步数补充的时候再增加我们的覆盖范围。如何增加覆盖范围呢?cover=Math.max(i+nums[i],cover),i+nums[i] 就是我们的最新覆盖范围,但我们新的覆盖范围要比原来的覆盖范围 cover 大才去更新,这样才是我们要的。
  6. 如果 cover>=nums.length-1,就是到达最后一个下标的位置了,就 return true。如果结束循环了也没找到那就是 false 了

2.2 代码

//
class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        //覆盖范围, 初始覆盖范围应该是0,因为下面的迭代是从下标0开始的
        int coverRange = 0;
        //在覆盖范围内更新最大的覆盖范围
        for (int i = 0; i <= coverRange; i++) {
            coverRange = Math.max(coverRange, i + nums[i]);
            if (coverRange >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}

3. LeetCode 45. 跳跃游戏 II

3.1 思路

  1. 根据题目的 nums 数组我们可以知道在当前位置可以往前跳几步,这题问的是最少跳多少步可以到我们的终点位置,默认起始位置是下标 0 的位置。
  2. 本题的贪心思路:尽可能的去增加我的覆盖范围,用最少的步数去增加我的覆盖范围,一旦覆盖了终点,就输出步数即可
  3. 局部最优:当前可移动距离尽可能多走,如果还没到终点,步数再加一
  4. 整体最优:一步尽可能多走,从而达到最少步数
  5. if(nums.length==1)就 return 0,因为起点就是终点。然后定义当前的覆盖范围 cur=0,下一步的覆盖范围 next ,一旦当前的覆盖范围 cur 到头了就启动下一步的覆盖范围 next。定义个 result 记录需要的步数。
  6. for(int i=0; i<nums.length; i++)在循环一开始就要收集下一步的覆盖范围 next 了,next=Math.max(i+nums[i],next),这里只记录最远的覆盖范围。if(i==cur)这里的意思是 i 走到了当前的覆盖范围的终点。再继续判断 if(cur!=nums.length-1)这里的意思是这个位置还不是当前数组的终点,此时就要再继续走一步了也就是 result++,然后 cur 更新 next 即为下一步的覆盖范围,如果是说明 cur 已经覆盖终点了那就 break。前面如果不是终点,在更新了 result 和 cur 之后,再在这里判断 if(cur>=nums.length-1)这里意思是当前覆盖范围已经覆盖终点了,就 break。
  7. 最后 return result 就行

3.2 代码

//
class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return 0;
        }
        //记录跳跃的次数
        int count=0;
        //当前的覆盖最大区域
        int curDistance = 0;
        //最大的覆盖区域
        int maxDistance = 0;
        for (int i = 0; i < nums.length; i++) {
            //在可覆盖区域内更新最大的覆盖区域
            maxDistance = Math.max(maxDistance,i+nums[i]);
            //说明当前一步,再跳一步就到达了末尾
            if (maxDistance>=nums.length-1){
                count++;
                break;
            }
            //走到当前覆盖的最大区域时,更新下一步可达的最大区域
            if (i==curDistance){
                curDistance = maxDistance;
                count++;
            }
        }
        return count;
    }
}
目录
打赏
0
0
0
0
9
分享
相关文章
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
近端策略优化(PPO)是深度强化学习中高效的策略优化方法,广泛应用于大语言模型的RLHF训练。PPO通过引入策略更新约束机制,平衡了更新幅度,提升了训练稳定性。其核心思想是在优势演员-评论家方法的基础上,采用裁剪和非裁剪项组成的替代目标函数,限制策略比率在[1-ϵ, 1+ϵ]区间内,防止过大的策略更新。本文详细探讨了PPO的基本原理、损失函数设计及PyTorch实现流程,提供了完整的代码示例。
133 10
近端策略优化(PPO)算法的理论基础与PyTorch代码详解
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
100 1
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
6月前
|
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
77 6
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
147 2
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
102 1
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口