【算法之贪心算法IV】leetcode56. 合并区间-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法之贪心算法IV】leetcode56. 合并区间。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

力扣题目链接

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end，且满足 xstart ≤ x ≤ x``end，则该气球会被引爆。可以射出的弓箭的数量 没有限制 。弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数 。

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

解题思路

按照结束边界进行排序
如果前一个结束边界和后一个开始边界不相交，使用箭的数量加一，更新边界值。
不能用数值相减来判断大小，可能会出现出界的情况。

Java实现

方式一

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] point1, int[] point2) {
                return point1[1] < point2[1] ? -1 : 1;
            }
        });
        int pos = points[0][1];
        int ans = 1;
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > pos) {
                ans++;
                pos = points[i][1];
            }
        }
        return ans;
    }
}

方式二

class Solution {
    public int findMinArrowShots(int[][] points) {
                Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] point1, int[] point2) {
                return point1[0] < point2[0] ? -1 : 1;
            }
        });
        int count = 1;
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > points[i - 1][1]) {
                count++;
            } else {
                points[i][1] = Math.min(points[i - 1][1], points[i][1]);
            }
        }
        return count;
    }
}

435. 无重叠区间

力扣题目链接

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

解决思路

使用动态规划，res[i]表示以第i个区间为结束区间，最大的不重叠区间的个数。公式推导。
贪心算法。

Java实现

方式一：

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[1], o2[1]);
            }
        });
        int n = intervals.length;
        int pos = intervals[0][1];
        int res = 1;
        for (int i = 1; i < n; i++) {
            if (intervals[i][0] >= pos) {
                res++;
                pos = intervals[i][1];
            }
        }
        return n - res;
    }
}

方式二：

class Solution {

    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[0], o2[0]);
            }
        });
        int n = intervals.length;
        int[] res = new int[n];
        Arrays.fill(res, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (intervals[j][1] <= intervals[i][0]) {
                    res[i] = Math.max(res[j] + 1, res[i]);
                }
            }
        }
        return n - Arrays.stream(res).max().getAsInt();
    }
}

763.划分字母区间

力扣题目链接

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

解决思路

保证所有出现的字符最开始的元素和最后的元素都在一个片段中。

Java实现

class Solution {
    public List<Integer> partitionLabels(String s) {
        int start=0, end = 0;
        int len = s.length();
        int[] data = new int[26];
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            data[s.charAt(i) - 'a'] = i;
        }
        for (int i = 0; i < len; i++) {
            end = Math.max(data[s.charAt(i) - 'a'], end);
            if (i == end) {
                res.add(end - start + 1);
                start = end + 1;
            }
        }
        return res;
    }
}

56. 合并区间

力扣题目链接

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

解决思路

使用链表。判断是否有重合区间。

Java区间

class Solution {
    public int[][] merge(int[][] intervals) {
        LinkedList<int[]> res = new LinkedList<>();
        Arrays.sort(intervals, (a, b) -> {
            return Integer.compare(a[0], b[0]);
        });
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= res.getLast()[1]) {
                res.getLast()[1] = Math.max(res.getLast()[1], intervals[i][1]);
            } else {
                res.add(intervals[i]);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

738.单调递增的数字

力扣题目链接

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回小于或等于 n 的最大数字，且数字呈 单调递增 。

输入: n = 332
输出: 299

解决思路

找到数组中第一个元素比前面一个元素小的
前面一个元素的值减一，start--，直到前面元素小于等于当前元素。
更新start+1到最后的元素，都改为9。
1221的最大元素是1199。

Java实现

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        int start = 1;
        while (start < s.length() && chars[start - 1] <= chars[start]) {
            start++;
        }
        //找到数组中第一个元素比前一个元素大
        if (start < s.length()) {
            while (start > 0 && chars[start - 1] > chars[start]) {
                chars[start - 1]--;
                start--;
            }

            for (int i = start + 1; i < chars.length; i++) {
                chars[i] = '9';
            }
        }
        return Integer.parseInt(new String(chars));

    }
}

968.监控二叉树

力扣题目链接

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。

解决思路

覆盖就是当前节点是否被照亮。
当子节点有一个没有被覆盖，那么当前节点必须要点灯；当子节点都亮了，那么当前节点最好是无覆盖（当前节点在当前子树上是无覆盖的，如果还有父节点，让父节点点灯；如果当前节点是根节点，根据定义，根节点也需要点灯）

Java实现

class Solution {

    int count = 0;

    public int minCameraCover(TreeNode root) {
        if (minCame(root) == 0) {
            count++;
        }
        return count;
    }

    /**
     * 0  无覆盖  1 有摄像头   2  覆盖
     *
     * @param root
     * @return
     */
    public int minCame(TreeNode root) {
        if (root == null) {
            //空节点默认是有覆盖，避免在叶子节点上放摄像头
            return 2;

        }
        int left = minCame(root.left);
        int right = minCame(root.right);
        if (left == 2 && right == 2) {
            return 0;
        } else if (left == 0 || right == 0) {
            count++;
            return 1;
        } else {
            return 2;
        }

    }
}