Day 28 贪心算法 Part02

55. 跳跃游戏

这道题我是从后往前做的，但由于用了递归，速度会慢一些，但整体时间复杂度也是O(N)。

我的思路其实就是找到最后一个可以到达目标位置处的下标，如果不存在这样的位置，就说明最后一个位置不可达。假设找到了，我们就需要去判断找到的这个位置是否可达，此时它的可达性与最后一个位置的可达性是完全一致的（这是我这个思路最重要的点）。具体的看注释。

class Solution {
    public boolean canJump(int[] nums) {
        return findLast(nums, nums.length-1); 
    }
    public boolean findLast(int[] nums, int target){ //找到最后一个能够到达target的位置，如果没有这样的位置返回false
        if(target == 0) return true; //递归出口
        int last = target - 1;
        while(last >= 0 && nums[last] < target - last){
            last--;
        }
        if(last < 0) return false; //没有节点能到达target
        return findLast(nums, last); //如果找到了，则去判断last是否可达，如果last可达target一定可达，last不可达，target也不可达
    }
}

还是贴上一份官解的，从前往后遍历的思路也很简单，只是我当时没有想到。

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

45. 跳跃游戏 II

先写我自己的思路吧，代码真的很丑，调了好久才全通过了。使用cnt记录步数。从起点开始，每次在其覆盖位置内，找到下一个节点，使得覆盖范围最远。所以代码中最关键的部分就是找到这个节点。

class Solution {
    public int jump(int[] nums) {
        int cnt = 0;
        int start = 0;
        while(start < nums.length - 1){
            int maxRange = start + nums[start];
            if(maxRange >= nums.length - 1) return ++cnt;  //如果已经可以覆盖终点，直接返回
            // 找到下一个覆盖范围最远的节点
            int nextStart = start, tmpMax = maxRange; //tmpMax记录最远可达的位置
            for(int i = start+1; i <= maxRange; i++){
                if(i+nums[i] > tmpMax) { //当找到更远的位置，更新tmpMax和nextStart
                    tmpMax = i + nums[i];
                    nextStart = i;
                }
            }
            start = nextStart;
            cnt++;
        }
        return cnt;
    }
}

题解的思路真是又清楚，代码又简练啊，我的妈，差距怎么这么大。思路其实是差不多的，但是这样写出来就是非常简练。

class Solution {
    public int jump(int[] nums) {
        if(nums.length == 1) return 0;
        int curRange = 0; // 当前覆盖的最远位置
        int step = 0;
        int nextRange = 0; // 下一步覆盖最远位置
        for(int i = 0; i < nums.length; i++){
            if(curRange >= nums.length - 1) break; //如果已经覆盖了最后一个位置
            nextRange = Math.max(nextRange, i + nums[i]);
            if(curRange == i){
                curRange = nextRange;
                step++;
            }
        }
        return step;
    }
}

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

即便是简单题，我写的也是依托啊。没脸贴自己的代码了，直接放下面看到的题解。

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 排序，把可能有的负数排到前面
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            // 贪心：如果是负数，而k还有盈余，就把负数反过来
            if (nums[i] < 0 && k > 0) {
                nums[i] = -1 * nums[i];
                k--;
            }
            sum += nums[i];
        }
        Arrays.sort(nums);
        // 如果k没剩，那说明能转的负数都转正了，已经是最大和，返回sum
        // 如果k有剩，说明负数已经全部转正，所以如果k还剩偶数个就自己抵消掉，不用删减，如果k还剩奇数个就减掉2倍最小正数。
        return sum - (k % 2 == 0 ? 0 : 2 * nums[0]); 
    }
}