深圳市招聘网站,网站页面的宽度,如何做优秀的视频网站设计,建设注册中心网站首页目录 买卖股票的最佳时机II跳跃游戏跳跃游戏ii LeetCode 122.买卖股票的最佳时机II LeetCode 55. 跳跃游戏 LeetCode 45.跳跃游戏II
买卖股票的最佳时机II
只有一只股票#xff01;
当前只有买股票或者卖股票的操作。
最终利润是可以分解的#xff1a;把利润分解为每天为… 目录 买卖股票的最佳时机II跳跃游戏跳跃游戏ii LeetCode 122.买卖股票的最佳时机II LeetCode 55. 跳跃游戏 LeetCode 45.跳跃游戏II
买卖股票的最佳时机II
只有一只股票
当前只有买股票或者卖股票的操作。
最终利润是可以分解的把利润分解为每天为单位的维度。
根据 prices 可以得到每天的利润序列(prices[i] - prices[i - 1])…(prices[1] - prices[0])。 其实我们需要收集每天的正利润就可以收集正利润的区间就是股票买卖的区间而我们只需要关注最终利润不需要记录区间。
那么只收集正利润就是贪心所贪的地方
局部最优收集每天的正利润全局最优求得最大利润。
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;}
}跳跃游戏
给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。
跳几步无所谓宗旨是 跳跃覆盖范围究竟可不可以覆盖到终点
贪心算法局部最优解每次取最大跳跃步数取最大覆盖范围整体最优解最后得到整体最大覆盖范围看是否能到终点。 i 的移动范围 max cover i 判断 max cover nums.length - 1 ? 直接 return true;
class Solution {public boolean canJump(int[] nums) {int cover 0;if (nums.length 1) return true;for (int i 0; i cover; i) {cover Math.max(cover, i nums[i]);if (cover nums.length - 1) return true;}return false;}
}这道题目关键点在于不用拘泥于每次究竟跳几步而是看覆盖范围覆盖范围内一定是可以跳过来的不用管是怎么跳的。
跳跃游戏ii
本题要计算最少步数。
局部最优当前可移动距离尽可能多走如果还没到终点步数再加一。整体最优一步尽可能多走从而达到最少步数。
但在写代码的时候还不能真的能跳多远就跳多远那样就不知道下一步最远能跳到哪里了。
真正解题的时候要从覆盖范围出发不管怎么跳覆盖范围内一定是可以跳到的以最小的步数增加覆盖范围覆盖范围一旦覆盖了终点得到的就是最少步数
这里需要统计两个覆盖范围当前这一步的最大覆盖和下一步最大覆盖。 图中覆盖范围的意义在于只要红色的区域最多两步一定可以到
移动下标达到了当前覆盖的最远距离下标时步数就要加一来增加覆盖距离。最后的步数就是最少步数。
class Solution {public int jump(int[] nums) {int curCover 0;int nextCover 0;int result 0;if (nums.length 1) return 0;for (int i 0; i nums.length; i) {nextCover Math.max(nextCover, i nums[i]);// 更新下一步覆盖最远距离下标if (i curCover) { // 遇到当前覆盖最远距离下标result;curCover nextCover; //更新当前覆盖最远距离下标if (nextCover nums.length - 1) break;}}return result;}
}理解本题的关键在于以最小的步数增加最大的覆盖范围直到覆盖范围覆盖了终点
