数据结构与算法-贪心算法

贪心算法是动态规划的特殊情况, 因为贪心的每一步都需要选择最优解. 满足贪心选择性质, 就可以用贪心.

区间调度问题

435. 无重叠区间

按右边界从小到大排序, 要求接下来的每一个区间的左边界大于等于这个右边界才能符合条件. 不符合条件的区间的区间数量就是答案.

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length <= 1) return 0;
        int res = 0;
        Arrays.sort(intervals, (a, b) -> {
            return a[1] - b[1];
        });
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) res++;
            else {
                end = intervals[i][1];
            }
        }
        return res;
    }
}

452. 用最少数量的箭引爆气球

和上一道题思路一样, 这里的lambda中没有直接相减, 因为负数减正数会导致溢出.

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length <= 1) return points.length;
        Arrays.sort(points, (a, b) -> {
            if (a[1] < b[1]) return -1;
            else if (a[1] > b[1]) return 1;
            else return 0;
        });
        int res = 1, end = points[0][1];

        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > end) {
                res++;
                end = points[i][1];
            }
        }
        return res;
    }
}

跳跃游戏

55. 跳跃游戏

在每个点算能跳到的最远距离, 直到到达最远距离或者在这个点只能原地踏步.

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

45. 跳跃游戏II

原理同上, 题目中假设总是可以到达数组的最后一个位置. 所以从第一个可到达的范围内, 选一个可以跳的最远的作为end, 记为一跳. 再重复此操纵, 直到跳完所有的点.

class Solution {
    public int jump(int[] nums) {
        int end = 0, res = 0, reach = 0;
        for (int i = 0; i < nums.length - 1; i++) { //最后一个点不算, 否则刚好跳到这个点就会多计算一次
            end = Math.max(end, i + nums[i]);
            if (reach == i) {
                res++;
                reach = end;
            }
        }
        return res;
    }
}