【力扣一刷】代码随想录day32(贪心算法part2:122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II )

本文主要是介绍【力扣一刷】代码随想录day32(贪心算法part2:122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II ),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

【122.买卖股票的最佳时机II】中等题

方法一  贪心算法

方法二  动态规划

【55. 跳跃游戏】中等题

【尝试】 递归 (超时)

方法  贪心算法

【45.跳跃游戏II】中等题

方法  贪心算法


【122.买卖股票的最佳时机II】中等题(偏简单)

方法一  贪心算法

思路:

1、局部最优:截止到当天能赚到的最大利润

2、全局最优:截止到最后一天能赚到的最大利润就是全局最大利润

例子:上升就是赚钱机会,贪心地将每个赚钱机会把握住,获取赚到的钱的总和即可

class Solution {public int maxProfit(int[] prices) {int res = 0;for (int i = 0; i < prices.length - 1; i++){int delta = prices[i + 1] - prices[i];if (delta > 0) res += delta; // 贪心算法,不放过截止到现在的所有赚钱机会}return res;}
}
  • 时间复杂度: O(n),for循环遍历一次数组
  • 空间复杂度: O(1),没有额外的空间开销

方法二  动态规划

思路:

1、确定dp[i]的含义:截止到第i天赚到的最多的钱

2、确定递推关系:dp[i] = dp[i-1] + today

3、确定初始值:第一天赚到的最多的钱肯定是0,即dp[0] = 0

class Solution {public int maxProfit(int[] prices) {int dp = 0;for (int i = 1; i < prices.length; i++){// 今天之前赚到的最多的钱 + 今天当天赚到最多的钱 = 包括今天在内已经赚到的最多的钱int today = prices[i] - prices[i-1] > 0 ? prices[i] - prices[i-1] : 0;dp += today;}return dp;}
}
  • 时间复杂度: O(n),for循环遍历一次数组
  • 空间复杂度: O(1),dp[i]只与dp[i-1]有关,只用一个变量记录值即可


【55. 跳跃游戏】中等题

【尝试】 递归 (超时)

思路:

1、确定参数和返回值:传入数组和起跳索引作为参数,返回值为起跳索引能否到达最后一个索引的判断结果。

2、确定终止条件:当起跳索引为最后一个索引时,证明能够到达最后一个下标,返回true

3、确定单层递归逻辑:先获取当前起跳索引 start 能跳到的范围,一般是 [start + 1, start + nums[start]]。只需要遍历这个范围,如果这个范围内存在能否到达最后一个索引的索引即可返回true;for遍历结束后,在这个范围内的索引都无法到达最后一个索引,则该起跳索引无法到达最后一个索引,返回false。 

class Solution {public boolean canJump(int[] nums) {return canJumpToEnd(nums, 0);}public boolean canJumpToEnd(int[] nums, int start){// 起跳索引到达最后一个索引if (start == nums.length - 1) return true;// 计算起跳索引能到达的索引范围,如果索引范围超过数组的可索引范围,则取数组最大索引int longest = Math.min(start + nums[start], nums.length - 1);// for循环遍历每个start可到达的索引,如果有一个索引能到达最后一个索引就返回truefor (int i = start + 1; i <= longest; i++){if (canJumpToEnd(nums, i)) return true;}// for遍历完之后都到不了,则说明该索引无法到达最后一个索引,返回falsereturn false;}
}

方法  贪心算法

思路:

1、局部最优即获取遍历到的索引的最大覆盖范围,全局最优即遍历到最后相当于获取所有索引的最大覆盖范围,只要判断全局覆盖范围是否包含最后一个索引即可。

2、for循环遍历最大覆盖范围,每遍历一个索引就更新一次最大覆盖范围,判断最大覆盖范围是否包含了最后一个索引,是则返回true;

3、如果在最大覆盖范围内的索引都遍历完了也到达不了最后一个索引,则返回false

class Solution {public boolean canJump(int[] nums) {int longest = 0;for (int i = 0; i <= longest; i++){longest = Math.max(longest, i + nums[i]); // 更新最大覆盖范围if (longest >= nums.length - 1){  // 如果能到达最后一个索引,则返回true,还可以避免数组索引越界return true;}}return false; // 如果在最大覆盖范围内的索引都遍历完了也到达不了最后一个索引,则返回false}
}
  • 时间复杂度: O(n),for循环遍历一次数组
  • 空间复杂度: O(1)


【45.跳跃游戏II】中等题(偏难)

方法  贪心算法

思路:

1、贪心策略:每跳一步,就贪心地获取这一步能到达的最远处,如果最远处超过最后一个索引,则一共所跳的次数就是最少的次数。

2、关键:如何获取每跳一步能到达的最远处?

例子:[2,3,1,2,4,2,3]      结果:3

  • 第①次跳,只能从 i = 0 处开始跳,所以第①次跳能到达的最远处为 i = 2,最远处还没越过最后一个索引。
  • 第②次跳,如果从 i = 1 处开始跳,能到达的最远处为 i = 4;如果从 i = 2 处开始跳,能到达的最远处为 i = 3;所以综合来看,第②次跳能到达的最远处为 i = 4,最远处还没越过最后一个索引。
  • 第③次跳,如果从 i = 3 处开始跳,能到达的最远处为 i = 5;如果从 i = 4 处开始跳,能到达的最远处为 i = 8;所以综合来看,第③次跳能到达的最远处为 i = 8,已经越过了最后一个索引 i = 6。

3、步骤分析:

  • 获取当前能到达的最远处。

  • 判断当前能到达的最远处是否能到达最后一个索引,如果计算完下一跳的边界前(或到达当前跳的边界前)就已经能到达最后一个索引,则还需要再跳一次再返回结果。

  • 如果上一跳能跳到的位置已经遍历完了(到达上一轮的边界时),则开启新一跳,次数+1,并设置新一跳的边界。

class Solution {public int jump(int[] nums) {int longest = 0;  // 用于记录已经遍历过的索引能到达的最远处int end = 0;  // 用于记录上一跳的边界/能到达的最远处int cnt = 0;  // 用于记录所跳的次数 for (int i = 0; i < nums.length - 1; i++){// 获取当前能到达的最远处longest = Math.max(longest, i + nums[i]);// 判断当前能到达的最远处是否能到达最后一个索引if (longest >= nums.length - 1){cnt++; // 如果计算完下一跳的边界前就已经能到达最后一个索引,则还需要再跳一次再返回结果break;}// 如果上一跳能跳到的位置已经遍历完了(到达上一轮的边界),则开启新一跳并设置新一跳的边界if (i == end){cnt++; // 开启新一跳,次数+1end = longest;  // 更新新一跳能到达的最远处/边界}}return cnt;}
}
  • 时间复杂度: O(n),for循环遍历一次数组
  • 空间复杂度: O(1)

这篇关于【力扣一刷】代码随想录day32(贪心算法part2:122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II )的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/887748

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格(JTable)作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.

基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

《基于HTML5Canvas实现图片旋转与下载功能(完整代码展示)》本文将深入剖析一段基于HTML5Canvas的代码,该代码实现了图片的旋转(90度和180度)以及旋转后图片的下载... 目录一、引言二、html 结构分析三、css 样式分析四、JavaScript 功能实现一、引言在 Web 开发中,

Python如何去除图片干扰代码示例

《Python如何去除图片干扰代码示例》图片降噪是一个广泛应用于图像处理的技术,可以提高图像质量和相关应用的效果,:本文主要介绍Python如何去除图片干扰的相关资料,文中通过代码介绍的非常详细,... 目录一、噪声去除1. 高斯噪声(像素值正态分布扰动)2. 椒盐噪声(随机黑白像素点)3. 复杂噪声(如伪

Java Spring ApplicationEvent 代码示例解析

《JavaSpringApplicationEvent代码示例解析》本文解析了Spring事件机制,涵盖核心概念(发布-订阅/观察者模式)、代码实现(事件定义、发布、监听)及高级应用(异步处理、... 目录一、Spring 事件机制核心概念1. 事件驱动架构模型2. 核心组件二、代码示例解析1. 事件定义