当前位置：首页 > article >正文

LeetCode刷题日记之贪心算法（五）

article 2024/10/27 2:51:52

前言

随着对贪心算法的不断深入，本篇文章将继续挑战一些经典的题目，进一步巩固这一算法的应用技巧。希望博主记录的内容能够帮助大家更好地掌握贪心算法的解题思路✍✍✍

无重叠区间

LeetCode题目链接

这道题就是给一个区间集合，然后让我们尽可能少地移除掉区间使得剩下的区间互不重叠

请添加图片描述

我们来思路梳理

我们可以先将每个区间的结束时间进行升序排序。这是因为希望保留结束时间早的区间，尽可能减少与后续区间的重叠🤔🤔🤔然后遍历排序后的区间，依次选择区间。每次选择时检查当前区间的起始时间是否大于等于前一个选择的区间的结束时间。如果是，则说明这两个区间不重叠；否则，就需要移除当前区间🤓🤓🤓在遍历过程中，记录不重叠的区间数量，最后用总区间数减去不重叠区间数即可得到最少需要移除的区间数量😀😀😀

很清楚的逻辑了，完整代码如下

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        //防止整数溢出方法排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        
        int prevEnd = intervals[0][1]; //初始化前序区间结束时间
        int removals = 0;//初始化需要移除区间的数量

        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] < prevEnd){ //如果有重叠
                removals++;
            }else{
                prevEnd = intervals[i][1];//更新状态
            }
        }

        return removals;
    }
}

划分字母区间

LeetCode题目链接

这道题就是说要尽可能划分多的字符串片段，每个字符串片段中的字母不会有重叠

请添加图片描述

我们来思路梳理

首先我们遍历字符串，记录每个字符在字符串中的最后出现位置🤔🤔🤔 然后我们开始从字符串的开头进行遍历，逐步扩展当前片段的结束位置。对于每个字符，我们将当前片段的结束位置更新为该字符的最后出现位置。如果当前遍历到的字符位置等于当前片段的结束位置，说明这个片段已经可以划分完毕🤓🤓🤓 当一个片段完成后，记录该片段的长度，继续从下一个字符开始划分新的片段，直到遍历完字符串😀😀😀

也是很清楚的逻辑了，完整代码如下

class Solution {
    public List<Integer> partitionLabels(String s) {
        //记录小写字符的最后出现位置
        int[] lastOccurrence = new int[26];
        for(int i = 0; i < s.length(); i++){
            lastOccurrence[s.charAt(i) - 'a'] = i;
        }

        List<Integer> result = new ArrayList<>();
        int start = 0;//初始片段起始位置
        int end = 0;//初始片段结束位置

        for(int i = 0; i < s.length(); i++){
            end = Math.max(end, lastOccurrence[s.charAt(i) - 'a']); //取遍历到的字符最后位置为片段结束位置

            if(i == end){//遍历到片段的结束位置
                result.add(end - start + 1);
                start = i + 1; //更新下一片段的起始位置
            }
        }
        return result;
    }
}

合并区间

LeetCode题目链接

这道题和无重叠区间题目类似，但是不是移除重叠区间而是合并重叠区间，使得合并后的区间不重叠，但这里的话就是区间相连也视作重叠区间要合并🤔🤔🤔

请添加图片描述

我们来思路梳理

将区间按照起始位置进行升序排序。这样可以保证处理时区间是从左到右有序的，方便合并重叠的区间🤔🤔🤔然后遍历排序后的区间，维护一个合并后的区间列表。如果当前区间的起始位置小于等于前一个合并区间的结束位置，说明它们重叠，则更新当前合并区间的结束位置为两个区间中较大的结束位置；否则，将当前区间加入合并后的结果列表😀😀😀

这道题的逻辑也比较清楚，完整代码如下

class Solution {
    public int[][] merge(int[][] intervals) {
        //按照区间起始位置安全排序
        Arrays.sort(intervals, (a,b) -> Integer.compare(a[0], b[0]));

        //使用链表存储合并后的区间
        LinkedList<int[]> merged = new LinkedList<>();

        for(int[] interval : intervals){
            //如果 merged 为空或当前区间与前一个区间不重叠，直接添加
            if(merged.isEmpty() || merged.getLast()[1] < interval[0]){
                merged.add(interval);
            }else{
                //合并当前区间和前一个区间，更新结束位置
                merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]);
            }
        }

        //将链表转换为二维数组返回
        return merged.toArray(new int[merged.size()][]);
    }
}

可能会有所疑问的部分

这里用链表来存储和普通数组列表有什么区间呢？🤔🤔🤔
- 因为这里是一个不断添加删除和删除的场景，需要频繁地插入新的区间，LinkedList在插入操作上比ArrayList更高效，在列表处理的时候根据频繁访问还是频繁插入选择合适的列表数据结构😀😀😀

单调递增的数字

LeetCode题目链接

这道题就是返回一个小于或等于整数n的最大单增数，所谓的单调递增数是指从左至右相邻数x和y满足x<=y

请添加图片描述

我们来思路梳理

最优解是要找到小于或等于 n 的最大单调递增数字。我们需要从右往左扫描数字，找到第一个不满足单调递增的地方，从那个地方开始进行调整🤔🤔🤔 从右往左检查，如果发现某一位数字比下一位大，就将该位减 1，同时将它右边所有的数字变成 9，以保证数字尽可能大且是单调递增的😀😀😀

思路梳理的很清楚了，完整代码如下

class Solution {
    public int monotoneIncreasingDigits(int n) {
        //将数字转换为字符数组方便进行逐位操作
        char[] num = Integer.toString(n).toCharArray();
        int length = num.length;

        //从右往左遍历，找到不满足单调递增的地方
        int maker = length;
        for(int i = length - 1; i > 0; i--){
            if(num[i] < num[i - 1]){
                num[i - 1]--;
                maker = i;//标记不满足单调递增的地方，后面要变成9
            }
        }

        //将标记后的所有数字设置为9
        for(int i = maker; i < length; i++){
            num[i] = '9';
        }

        return Integer.parseInt(new String(num));
    }
}

可能存在的不易理解的问题

为什么只需要找一次 marker 并把后面数字变为 9🤔🤔🤔
这是因为当我们发现某个位置的数字不满足单调递增时，我们贪心地把前一位数字减 1，然后从这一位的后面所有数字全部变成 9，这样可以确保得到的数字尽可能大，且保持单调递增。如果在某一位减 1 后的调整仍然不满足单调递增，继续扫描之前的数字并进行调整即可。关键是，所有发生问题的数字调整后，其后的部分都应该变为 9，这样我们只需要在扫描过程中标记一次 marker，并统一将后面的数字变为 9😀😀😀

监控二叉树

LeetCode题目链接

就是给个二叉树，然后的话给二叉树中的一个节点安装摄像头，这个摄像头可以监控节点自身、父节点和子节点要求返回监控整个二叉树的最少摄像头数量

请添加图片描述

我们来思路梳理

这道题可以通过贪心算法结合后序遍历来解决🤔🤔🤔 为了确保用最少的摄像头覆盖所有节点，我们优先从叶子节点开始考虑放置摄像头。如果某个节点的子节点尚未被覆盖，那么我们必须在该节点放置摄像头。通过后序遍历自底向上进行，确保每次都能局部最优地选择摄像头位置😀😀😀 使用后序遍历的方式，从叶子节点开始遍历，递归地决定是否在当前节点放置摄像头。这样可以确保每个节点和它的子节点都能被覆盖

逻辑梳理的比较清楚了，完整代码如下

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private static final int NOT_COVERED = 0;//节点未被覆盖
    private static final int COVERD_NO_CAMERA = 1;//节点被覆盖但没有摄像头
    private static final int HAS_CAMERA = 2;//节点安装了摄像头

    private int cameraCount = 0;//记录安装摄像头的数量

    public int minCameraCover(TreeNode root) {
        // 如果根节点未被覆盖，则在根节点安装摄像头
        if (dfs(root) == NOT_COVERED) {
            cameraCount++;
        }
        return cameraCount;
    }

    private int dfs(TreeNode root){
        if(root == null) return COVERD_NO_CAMERA;//空节点视为已覆盖

        int left = dfs(root.left);
        int right = dfs(root.right);

        //如果左或右子节点未被覆盖，则当前节点需要安装摄像头
        if(left == NOT_COVERED || right == NOT_COVERED){
            cameraCount++;
            return HAS_CAMERA;
        }

        //如果任意子节点有摄像头，则当前节点已被覆盖，无需安装摄像头
        if(left == HAS_CAMERA || right == HAS_CAMERA){
            return COVERD_NO_CAMERA;
        }

        //如果子节点都被覆盖但没有摄像头，则当前节点未被覆盖
        return NOT_COVERED;
    }
}