第八章 贪心算法 part02

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

本题解法很巧妙，本题大家可以先自己思考一下然后再看题解，会有惊喜！
文章讲解

思路

• 把利润分解为每天的维度，只收集正利润

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) {
        int cover = 0;
        if(nums.length == 1) return true;
        for(int i = 0; i <= cover; i++){
            cover = Math.max(i + nums[i], cover);
            if(cover >= nums.length-1) return true;
        }
        return false;
    }
}

45.跳跃游戏II

本题同样不容易想出来。贪心就是这样，有的时候 会感觉简单到离谱，有时候，难的不行，主要是不容易想到。
文章讲解

思路

• 尽可能跳最大值，但是写代码时不能这样实现。
• 比如 [2,3,1,1,4]，在最开始的位置不能跳两步，而是应该先跳到3的位置
• 依然是用尽量少的步数来增加更多覆盖范围。只记录下一步最大的覆盖范围。

class Solution {
    public int jump(int[] nums) {
        if (nums.length == 1) return 0;
        int curDistance = 0;    // 当前覆盖最远距离下标
        int nextDistance = 0;   // 下一步覆盖最远距离下标
        int result = 0;            // 记录走的最大步数
        for(int i = 0; i < nums.length; i++){  //开始遍历数组，收集下一步能跳多远
            nextDistance = Math.max(nums[i] + i, nextDistance); //只记录最远的记录
            if(i == curDistance){ //i移动到了当前的覆盖范围之后，发现也没有到终点，要再走一步到终点
                if(curDistance < nums.length-1){  // 当前的范围小于数组长度，必须要再走一步增加覆盖范围
                    result++;
                    curDistance = nextDistance;

                    // 如果当前覆盖范围已经到达或超过数组的最后一个元素，退出循环
                    if (curDistance >= nums.length - 1) {
                        break;
                    }
                }
            }
            
        }
        return result;
    }
}

但实际上代码随想录的少一个if

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

本题简单一些，估计大家不用想着贪心 ，用自己直觉也会有思路。
文章讲解

思路
第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
第二步：从前向后遍历，遇到负数将其变为正数，同时K--
第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
第四步：求和

• 注意一下Lambda表达式

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 对数组按绝对值从大到小排序
        //nums = Arrays.sort(nums, (a, b) -> Integer.compare(Math.abs(b), Math.abs(a)));  不能这样写
        nums = IntStream.of(nums)
                     .boxed()
                     .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                     .mapToInt(Integer::intValue)
                     .toArray();
        //绝对值从大到小排列  因为
        // Integer.compare(x, y) 方法比较两个整数 x 和 y：如果 x < y，返回负数（表示 a 应该排在 b 前面）。如果 x == y，返回 0（表示 a 和 b 的顺序不变）。如果 x > y，返回正数（表示 b 应该排在 a 前面）。
        // 依次将负数变为正数，优先处理绝对值最大的
        for(int i = 0; i < nums.length && k > 0; i++){ // 注意这里还有K>0
            if(nums[i] < 0){
                nums[i] = - nums[i];
                k--;
            }
        }
        // 如果K还大于0，且K是奇数，转变数值最小的元素, 因为如果k是偶数，正负转换结果不变
        if(k % 2 == 1) nums[nums.length - 1] = -nums[nums.length - 1];

        //计算结果  将数组 nums 转换为一个 IntStream 对象再求sum
        int sum = Arrays.stream(nums).sum();
        return sum;
    }
}