122.买卖股票的最佳时机II
题目链接：
思路
要使用贪心算法，首先要能把问题分解成局部最优，然后才能找到合适得贪心策略，按照一般贪心算法的四步分析这道题目
首先要明确条件：
只有一只股票
当前只有买股票和卖股票的操作
当天可以买，可以卖
想要获得利润只要要以两天为单位
1、将问题分解成若干个子问题
假设在第1天买入股票，在第4天买出股票所获得的利润更大，那么就是 prices[3] - prices[0] ,这个式子可以分解成（prices[3] - prices[2]）+（prices[2] - prices[1]）+（prices[1] - prices[0]）,这样就把 全局利润最大 分解成 每两天的 利润最大
2、找到合适的贪心策略
但是如果收集每一天的利润，那可能会包含负利润的情况，那对于这种情况只要不收集就可以，只收集获取利润的两天
3、求解每个子问题的最优解
当天减去前一天大于0 就是最优解
4、将局部最优解堆叠成全局最优
筛选 加入
所以这道题目的
局部最优：每天获得的正利润
全局最优：整个区间获得的最大利润
买卖股票的最佳时机||
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; } }
55. 跳跃游戏
题目链接：力扣
思路
真的很难想到思路，如果想分析清楚各种情况的跳跃是不太可能的，最关键要想到：其实跳几步是无所谓的，关键在于可跳的覆盖范围
在可覆盖的范围中，不论是怎么跳跃，都是可以跳跃到的，所以最终转换为跳跃范围究竟可不可以覆盖终点
局部最优：每次取最大跳跃步数（获取当前可以覆盖的最大范围）
全局最优：可不可以覆盖到重点
跳跃游戏
class Solution { public boolean canJump(int[] nums) { // 可以覆盖到的范围 int cover = 0; for (int i = 0; i <= cover; i++) { cover = Math.max(i + nums[i],cover); if (cover >= nums.length - 1) { return true; } } return false; } }
45.跳跃游戏II
题目链接：https://leetcode.cn/problems/jump-game-ii/submissions/
思路
本题要计算的是最小步数，关键在于在什么情况下来记录步数。如果每一个下标跳跃的步数都没有跳满，那势必不是最小的步数，所以要尽量每一步跳最大的步数
如果跳过了下标的最大步数，还没有到达重点，那么就不要再前进一步
思路很巧妙，代码简单也很巧妙
遍历数组的时候，要获取当前下标数字可覆盖的最大范围
1.如果这个范围是可以覆盖重点的，那就代表只需要跳这个下标代表的步数就可以，这代表1步
2.如果这个范围不可以覆盖到重点，那就要看看有没有目前范围内有没有可以覆盖到的，如果遍历完还没有，那就说明继续往前扩大范围
跳跃游戏||
class Solution { public int jump(int[] nums) { if (nums == null || nums.length == 0 || nums.length == 1) { return 0; } // 记录跳跃的次数 int count = 0; // 当前的覆盖的最大区域 int curDistance = 0; // 可获得的最大覆盖区域 int maxDistance = 0; for (int i = 0; i < nums.length; i++) { // 获取可获得的最大覆盖区域 maxDistance = Math.max(maxDistance,i + nums[i]); if (maxDistance >= nums.length - 1) { count++; break; } //走到当前最大区域 还没有到达终点 if (i == curDistance) { curDistance = maxDistance; count++; } } return count; } }
