培训制作网站关键词的优化和推广
目录
【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)