重生之我在代码随想录刷算法第二十四天 | 122.买卖股票的最佳时机 II、55. 跳跃游戏、45.跳跃游戏 II

参考文献链接：代码随想录

本人代码是Java版本的，如有别的版本需要请上代码随想录网站查看。

122.买卖股票的最佳时机 II

力扣题目链接

解题思路

这道题目就是去买彩票获得最多利润，那局部最优解是什么？

就是在这部分里用最大的减了最小的。如果做到呢？

遍历数组先找最小的，当某一个数不再比前一个小，那么就从它开始找最大的，当某一个数不再更大，那么此时就是局部最优解。局部最优推出全局最优。

但是这种思想代码很不简洁，简单方法：

每次判断后一个和前一个的差，如果大于0差值就是利润，小于0那我们就不在这局部购买，利润就是0。把每个利润加起来即可。

代码示例

复杂方法：

class Solution {public int maxProfit(int[] prices) {if(prices.length == 1){return 0;}int max = Integer.MIN_VALUE;int min = prices[0];int flag = 0;int result = 0;for(int i = 1;i < prices.length;i++){if(flag == 0){if(prices[i] < min){min = prices[i];}else{flag = 1;max = prices[i];continue;}}if(flag == 1){if(prices[i] > max){max = prices[i];}else{System.out.println(max);System.out.println(min);result+= max - min;flag = 0;min = prices[i];}}}if(flag == 1){result += max - min;}return result;}
}

简单方法：

// 贪心思路
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) {if(nums.length == 1){return true;}//覆盖范围最开始是0下标对应的数字，比如说1，2，3，4这组数，最开始覆盖范围是1，就是数组下标(0,1)能到达。int countRange = nums[0];//循环条件是小于等于范围，如果走着走着走到范围终点范围还没更新，说明走不动了。for(int i = 1;i <= countRange;i++){//判断当前范围大还是i + nums[i]覆盖的大。 i+nums[i]就是某个下标对应的能走到的地方。countRange = countRange > i + nums[i] ? countRange : i + nums[i];//如果覆盖范围包含最后一个下标，则trueif(countRange >= nums.length - 1){return true;}}return false;}
}

45.跳跃游戏 II

力扣题目链接

解题思路

这道题目比上一题难一些，需要看它跳跃的最小次数。同样还是像上一题需要用到覆盖范围。这次遍历数组的同时，我们记录最大覆盖范围，再来一个变量记录当前覆盖范围，每当当前覆盖范围不够用，我们就把他更新成最大覆盖范围，这也就是跳跃了一次。

代码示例

class Solution {public int jump(int[] nums) {if(nums.length == 1){return 0;}int count = 0;int maxCountRange = nums[0];int countRange = nums[0];for(int i = 1;i < nums.length;i++){maxCountRange = maxCountRange > i + nums[i] ? maxCountRange : i + nums[i];if(countRange >= nums.length - 1){count++;break;}if(i == countRange){countRange = maxCountRange;count++;}}return count;}
}

1005.K次取反后最大化的数组和

力扣题目链接

解题思路

这道题比前几道简单一些，我的思路是先把数组排序然后把负数变正。k的剩余次数如果是奇数，那么就再次把数组排序然后把最小的取反。

代码示例

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {Arrays.sort(nums);int result = 0;for(int i = 0;k > 0 && i < nums.length;i++){if (nums[i] < 0) {nums[i] = -nums[i];k--;}}if(k % 2 == 1){Arrays.sort(nums);nums[0] = - nums[0];}for(int i = 0;i < nums.length;i++){result = result + nums[i];}return result;}
}