青岛专业制作网站,万能的搜索引擎,常德网站建设优化,设计师交流网站目录 【122.买卖股票的最佳时机II】中等题 方法一 贪心算法 方法二 动态规划 【55. 跳跃游戏】中等题 【尝试】 递归 #xff08;超时#xff09; 方法 贪心算法 【45.跳跃游戏II】中等题 方法 贪心算法 【122.买卖股票的最佳时机II】中等题#xff08;偏简单#xff0… 目录 【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]]。只需要遍历这个范围如果这个范围内存在能否到达最后一个索引的索引即可返回truefor遍历结束后在这个范围内的索引都无法到达最后一个索引则该起跳索引无法到达最后一个索引返回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)
