1. LeetCode 122. 买卖股票的最佳时机 II
1.1 思路
- 本题可以用贪心算法和动态规划解决。这里用贪心算法。本题中你买和卖分别是什么时候？多低时候买算低，多高时候卖算高？这些都不好把握，因此这思路不太好找。
- 以 prices 数组 [7,1,5,10,3,6,4] 为例，以 p[3]-p[0] 为例，是不是相当于 p3-p2+p2-p1+p1-p0。这一段区间就是相当于我每天的利润和，每天的利润有正有负，而只有正利润相加才对总利润有正向的作用，因此每天的利润就收集正的即可，以 prices 数组为例的利润数组 [-6,4,5,-7,3,-2] 这就是每天的利润组成的数组，这里只收集 4、5、3 就是我们的最大总利润，其实这里的 4、5 就相当于在 p1 买入 p3 卖出得到的利润，3 就相当于在 p4 买入 p5 卖出得到的利润。但此题不需要记录位置，只关注最大总利润
- 局部最优：只收集每天的正利润
- 全局最优：收集到的最大总利润。这样的思路找不出明显反例反驳
- 定义 result 收集每天的正利润，for(int i=1; i<price.length; i++)，i 为什么从 1 开始，我们收集每天的利润是不是起码要从下标 1 的位置才能减去昨天的价格得出当天的利润对吧。然后 result+=Math.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 步呢？跳到下一个元素了又应该跳几步呢？按照这个思路想就很难解出出来了。
- 我们可以换一个思路：我们不去纠结具体跳几步，只去看覆盖范围，如果在当前位置的覆盖范围能把终点覆盖了就是对了
- 局部最优：每次跳跃取最大跳跃步数（取最大覆盖范围）
- 全局最优：最后得到整体的最大覆盖范围，看是否能到终点
- 定义个 cover=0。如果数组长度就是 1 就是一定可以跳跃到的，因为最开始起始位置已经站在那了。 for(int i=0; i<=cover; i++)，注意这里是<=cover，因为我们遍历是在覆盖范围内遍历的，然后得到可跳跃的步数补充的时候再增加我们的覆盖范围。如何增加覆盖范围呢？cover=Math.max(i+nums[i]，cover)，i+nums[i] 就是我们的最新覆盖范围，但我们新的覆盖范围要比原来的覆盖范围 cover 大才去更新，这样才是我们要的。
- 如果 cover>=nums.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.length==1)就 return 0，因为起点就是终点。然后定义当前的覆盖范围 cur=0，下一步的覆盖范围 next ，一旦当前的覆盖范围 cur 到头了就启动下一步的覆盖范围 next。定义个 result 记录需要的步数。
- for(int i=0; i<nums.length; i++)在循环一开始就要收集下一步的覆盖范围 next 了，next=Math.max(i+nums[i]，next)，这里只记录最远的覆盖范围。if(i==cur)这里的意思是 i 走到了当前的覆盖范围的终点。再继续判断 if(cur!=nums.length-1)这里的意思是这个位置还不是当前数组的终点，此时就要再继续走一步了也就是 result++，然后 cur 更新 next 即为下一步的覆盖范围，如果是说明 cur 已经覆盖终点了那就 break。前面如果不是终点，在更新了 result 和 cur 之后，再在这里判断 if(cur>=nums.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 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; } }
