网站建设需要条件,常德做网站公司哪家好,儿童网站网页设计,wordpress添加新文章类型代码随想录算法训练营第三十二天 | LeetCode 122. 买卖股票的最佳时机 II、55. 跳跃游戏、45. 跳跃游戏 II 文章链接#xff1a;买卖股票的最佳时机 II 跳跃游戏 跳跃游戏 II 视频链接#xff1a;买卖股票的最佳时机 II 跳跃游戏 跳跃游戏 II 目…代码随想录算法训练营第三十二天 | LeetCode 122. 买卖股票的最佳时机 II、55. 跳跃游戏、45. 跳跃游戏 II 文章链接买卖股票的最佳时机 II 跳跃游戏 跳跃游戏 II 视频链接买卖股票的最佳时机 II 跳跃游戏 跳跃游戏 II 目录
代码随想录算法训练营第三十二天 | LeetCode 122. 买卖股票的最佳时机 II、55. 跳跃游戏、45. 跳跃游戏 II
1. LeetCode 122. 买卖股票的最佳时机 II
1.1 思路
1.2 代码
2. LeetCode 55. 跳跃游戏
2.1 思路
2.2 代码
3. LeetCode 45. 跳跃游戏 II
3.1 思路
3.2 代码 1. LeetCode 122. 买卖股票的最佳时机 II
1.1 思路 本题可以用贪心算法和动态规划解决。这里用贪心算法。本题中你买和卖分别是什么时候多低时候买算低多高时候卖算高这些都不好把握因此这思路不太好找。以 prices 数组 [7,1,5,10,3,6,4] 为例以 p[3]-p[0] 为例是不是相当于 p3-p2p2-p1p1-p0。这一段区间就是相当于我每天的利润和每天的利润有正有负而只有正利润相加才对总利润有正向的作用因此每天的利润就收集正的即可以 prices 数组为例的利润数组 [-6,4,5,-7,3,-2] 这就是每天的利润组成的数组这里只收集 4、5、3 就是我们的最大总利润其实这里的 4、5 就相当于在 p1 买入 p3 卖出得到的利润3 就相当于在 p4 买入 p5 卖出得到的利润。但此题不需要记录位置只关注最大总利润局部最优只收集每天的正利润全局最优收集到的最大总利润。这样的思路找不出明显反例反驳定义 result 收集每天的正利润for(int i1; iprice.length; i)i 为什么从 1 开始我们收集每天的利润是不是起码要从下标 1 的位置才能减去昨天的价格得出当天的利润对吧。然后 resultMath.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 思路 根据题目的 nums 数组我们可以知道在当前位置可以往前跳几步但比如这个位置数字是 3 的话我是跳 1 步 还是 2 步 还是 3 步呢跳到下一个元素了又应该跳几步呢按照这个思路想就很难解出出来了。我们可以换一个思路我们不去纠结具体跳几步只去看覆盖范围如果在当前位置的覆盖范围能把终点覆盖了就是对了局部最优每次跳跃取最大跳跃步数取最大覆盖范围全局最优最后得到整体的最大覆盖范围看是否能到终点定义个 cover0。如果数组长度就是 1 就是一定可以跳跃到的因为最开始起始位置已经站在那了。 for(int i0; icover; i)注意这里是cover因为我们遍历是在覆盖范围内遍历的然后得到可跳跃的步数补充的时候再增加我们的覆盖范围。如何增加覆盖范围呢coverMath.max(inums[i]cover)inums[i] 就是我们的最新覆盖范围但我们新的覆盖范围要比原来的覆盖范围 cover 大才去更新这样才是我们要的。如果 covernums.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 思路 根据题目的 nums 数组我们可以知道在当前位置可以往前跳几步这题问的是最少跳多少步可以到我们的终点位置默认起始位置是下标 0 的位置。本题的贪心思路尽可能的去增加我的覆盖范围用最少的步数去增加我的覆盖范围一旦覆盖了终点就输出步数即可局部最优当前可移动距离尽可能多走如果还没到终点步数再加一整体最优一步尽可能多走从而达到最少步数if(nums.length1)就 return 0因为起点就是终点。然后定义当前的覆盖范围 cur0下一步的覆盖范围 next 一旦当前的覆盖范围 cur 到头了就启动下一步的覆盖范围 next。定义个 result 记录需要的步数。for(int i0; inums.length; i)在循环一开始就要收集下一步的覆盖范围 next 了nextMath.max(inums[i]next)这里只记录最远的覆盖范围。if(icur)这里的意思是 i 走到了当前的覆盖范围的终点。再继续判断 if(cur!nums.length-1)这里的意思是这个位置还不是当前数组的终点此时就要再继续走一步了也就是 result然后 cur 更新 next 即为下一步的覆盖范围如果是说明 cur 已经覆盖终点了那就 break。前面如果不是终点在更新了 result 和 cur 之后再在这里判断 if(curnums.length-1)这里意思是当前覆盖范围已经覆盖终点了就 break。最后 return result 就行
3.2 代码
//
class Solution {public int jump(int[] nums) {if (nums null || nums.length 0 || nums.length 1) {return 0;}//记录跳跃的次数int count0;//当前的覆盖最大区域int curDistance 0;//最大的覆盖区域int maxDistance 0;for (int i 0; i nums.length; i) {//在可覆盖区域内更新最大的覆盖区域maxDistance Math.max(maxDistance,inums[i]);//说明当前一步再跳一步就到达了末尾if (maxDistancenums.length-1){count;break;}//走到当前覆盖的最大区域时更新下一步可达的最大区域if (icurDistance){curDistance maxDistance;count;}}return count;}
}
