算法训练营day27--122.买卖股票的最佳时机II +55. 跳跃游戏 +45.跳跃游戏 II+1005.K次取反后最大化的数组和

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

题目链接：https://leetcode.cn/problems/binary-search/description/
文章讲解：https://www.programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html
视频讲解：https://www.bilibili.com/video/BV1ev4y1C7na

1.1 初见思路

整体利润拆为每天的利润
只收集每天的正利润即可。

1.2 具体实现

class Solution {public int maxProfit(int[] prices) {int result = 0;for(int i=1;i<prices.length;i++){int curPrice = prices[i]-prices[i-1];if(curPrice>0){result+=curPrice;}}return result;}
}

1.3 重难点

二、 55. 跳跃游戏

题目链接：https://leetcode.cn/problems/jump-game/
文章讲解：https://www.programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html
视频讲解：https://www.bilibili.com/video/BV1VG4y1X7kB

2.1 初见思路

每跳到一个位置上就对应了下次能跳跃的所有范围内。

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;}
}

2.3 重难点

不要拘泥于我下次应该跳几步？是一步还是两步还是N步
突然想到这个题目好像就是跳楼梯的题目的变种，如果数组所有元素都是2，那么跳跃方式其实就跟跳楼梯的题目一致了。

三、45.跳跃游戏 II

题目链接：https://leetcode.cn/problems/jump-game-ii/
文章讲解：https://www.programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html
视频讲解：https://www.bilibili.com/video/BV1Y24y1r7XZ

3.1 初见思路

基于Q55 的思路，需要思考的问题如下
什么时候跳跃次数加1？----当本次覆盖范围遍历完后，就知道这次要跳到哪里了
还需要变量记录本次能覆盖的范围，并且要在本次覆盖范围遍历完时更新

3.2 具体实现

class Solution {public int jump(int[] nums) {int count = 0;int far=0;int cover=0;for(int i=0;i<=cover;i++){if(cover>=nums.length-1){return count;}far=Math.max(far,i+nums[i]);if(i==cover){cover=far;count++;}}return count;}
}

3.3 重难点

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

题目链接：https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
文章讲解：https://www.programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html
视频讲解：https://www.bilibili.com/video/BV138411G7LY

4.1 初见思路

把负数都变成正数，优先改变绝对值大的负数
如果所有负数都变成了正数，那就应该反复操作最小的正数。

4.2 具体实现

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {Arrays.sort(nums);int tempK = k;for(int i=0;i<nums.length && i<k;i++){if(nums[i]==0){break;}if(nums[i]<0){//从前向后遍历，遇到负数将其变为正数，同时K--nums[i]=-nums[i];tempK--;}}if(tempK>0){// 如果tempK还大于0，那么反复转变数值最小的元素，将tempK用完boolean flag = tempK%2==1?true:false;Arrays.sort(nums);if(flag){nums[0]=-nums[0];}}int sum=0;for(int i=0;i<nums.length;i++){sum+=nums[i];}return sum;}
}