Leetcode-day27-贪心算法

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

假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！

那么根据 prices 可以得到每天的利润序列：(prices[i] - prices[i - 1]).....(prices[1] - prices[0])。

class Solution {public int maxProfit(int[] prices) {//贪心：prices = [1,2,3,4,5]//比如要在第一天买入，最后一天卖出。prices[4]-prices[0]=prices[4]-prices[3]+prices[3]-prices[2]+prices[2]-prices[1]+prices[1]-prices[0]//所以我们可以把买入卖出的利润算出来，贪心：如果是正的，就累加，负的就舍弃。此时的局部最优就是单天的利润int[] profits = new int[prices.length-1];int res = 0;for(int i=0;i<prices.length-1;i++){profits[i] = prices[i+1] - prices[i];if(profits[i]>0){res = res+profits[i];}}return res;}
}

55. 跳跃游戏

这个题关键是想清楚思路：转换为覆盖范围，不断改变最大覆盖范围，如果能覆盖到最后，就true

跳跃覆盖范围究竟可不可以覆盖到终点！

每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

i 每次移动只能在 cover 的范围内移动，每移动一个元素，cover 得到该元素数值（新的覆盖范围）的补充，让 i 继续移动下去。

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

45. 跳跃游戏 II

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

贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。

那么如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和 达到最大。

那么又是一个贪心：局部最优：只找数值最小的正整数进行反转，当前数值和可以达到最大（例如正整数数组{5, 3, 1}，反转1 得到-1 比 反转5得到的-5 大多了），全局最优：整个 数组和 达到最大。

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {//1. 按照绝对值从大到小排序//2. 从左往右走，碰到负的就 -//3. 负数找完如果k还是大于0，就把最右边(绝对值最小的)做k次-int temp;for (int i = 0; i < nums.length; i++) {for (int j = 1; j < nums.length-i; j++) {if(Math.abs(nums[j-1])<Math.abs(nums[j])){temp=nums[j-1];nums[j-1]=nums[j];nums[j]=temp;}}}for (int i = 0; i < nums.length; i++) {if(k>0&&nums[i]<0){nums[i]=nums[i]*-1;k--;}}if(k%2==1){nums[nums.length-1]*=-1;}return Arrays.stream(nums).sum();}
}