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

题目链接：leetcode 122.买卖股票的最佳时机II

题目分析

注意到利润是可以分解的，如第1天买入第3天卖出的利润为prices[3]-prices[1]=(prices[3]-prices[2])+(prices[2]-prices[1])，相当于每天可以自由选择买卖且可以同时选择买卖，这样只需要计算每天与前一天的价格差，若为正计入总的利润。

代码

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

☆☆☆☆☆leetcode 55. 跳跃游戏

题目链接：leetcode 55. 跳跃游戏

题目分析

本题定义cover为当前覆盖范围（当前步数可走的最远距离），并保持更新，即每走一步计算当前可到的最远距离，若cover达到了末尾返回true，若走到了cover还没到达则返回false。

代码

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

☆☆☆☆☆leetcode 45.跳跃游戏II

题目链接：leetcode 45.跳跃游戏II

题目分析

本题定义cur为当前可走的最远距离，max为下一步可走的最远距离，count为最终结果结束。若i到达cur，则计数count加一并将max赋值给cur，若cur到达末尾，则结束循环返回count。

代码

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

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

题目链接：leetcode 1005.K次取反后最大化的数组和

题目分析

1.直接思路，将数组排序后，对最小的数取相反数，并重复k次，结束后依次遍历计算得到数组的和；
2.考虑到数组中经过一定次数的转换没有负数时，需要转换次数只集中在最小的正数或者0上，此时可以考虑讨论降低复杂度。首先，将数组排序，并依次将前面的负数取相反数，没变换依次k减一，直到k次用完减到0或者没有负数。然后，如果还有剩余的次数，若剩余次数k为偶数，只需将最小的正数重复取相反数偶数次，相当于没变，则无需处理；若剩余次数k为奇数，只需将最小的正数重复取相反数奇数次，相当于变换一次，则直接将最小的正数取相反数；最后，依次遍历计算得到数组的和；

代码

1.直接思路
class Solution {public int largestSumAfterKNegations(int[] nums, int k) {for(int i=0;i<k;i++){Arrays.sort(nums);nums[0]*=-1;}int res=0;for(int num:nums)res+=num;return res;}
}

2.降低复杂度版本
class Solution {public int largestSumAfterKNegations(int[] nums, int k) {Arrays.sort(nums);for(int i=0;i<nums.length&&k>0;i++){if(nums[i]<0){nums[i]*=-1;k--;}}if(k>0&&k%2==1){Arrays.sort(nums);nums[0]*=-1;}int res=0;for(int num:nums)res+=num;return res;}
}