算法训练营（day36）

贪心算法理论基础

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

举个例子，在规定次数内从一堆钞票里怎么拿面额最大的钞票，根据贪心算法的思想：每次拿最大的就好（够贪就行O(∩_∩)O）

贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

总而言之，贪心算法的本质其实就是 找到局部最优解，再比较所有的局部最优，得到全局最优。

435. 无重叠区间

题目链接：https://leetcode.cn/problems/non-overlapping-intervals/description/

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

解题思路

解题过程：贪心

1. 先对 starti进行排序

2. 比较 右边界 和 下一个 start 是否有重合

   • 有重合则 count 增加1，右边界更新为 两个区间右边界的最小值，扩大保留区间的可能性
   • 无重合则更新右边界为下一个区间的 end

3. 返回 count

详细代码

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            return Integer.compare(a[0], b[0]);
        });
        int count = 0;
        int end = intervals[0][1];

        for(int i = 1; i < intervals.length; i++){
            if(end > intervals[i][0]){
                count++;
                end = Math.min(end, intervals[i][1]);
            }else{
                end = intervals[i][1];
            }
        }
        return count;
    }
}

763. 划分字母区间

题目链接：https://leetcode.cn/problems/partition-labels/description/

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

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

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

解题思路

解题过程：贪心

1. 局部最优：为确保 同一字母最多出现在一个片段中，要确定每个字母 最后 出现的下标
2. 全局最优：当遍历到 字母最后出现的下标 时，将下标以前的字符串长度放入 list 中返回

详细代码

class Solution {
    public List<Integer> partitionLabels(String s) {
        LinkedList<Integer> list = new LinkedList<>();
        int[] edge = new int[26];
        char[] chars = s.toCharArray();
        for(int i = 0; i < chars.length; i++){
            edge[chars[i] - 'a'] = i;
        }

        int index = 0;
        int last = -1;
        for(int i = 0; i < chars.length; i++){
            index = Math.max(index, edge[chars[i] - 'a']);
            if(i == index){
                list.add(i - last);
                last = i;
            }
        }
        return list;
    }
}

56. 合并区间

题目链接：https://leetcode.cn/problems/merge-intervals/description/

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

解题思路

解题过程：贪心

1. 先将数组根据 start 进行排序

2. 比较 右边界 和 下一个 start 是否有重合

   • 有重合则将右边界更新为 下一个区间的 end ，更新 result
   • 无重合则将当前区间直接放入 result 中

3. 返回 result

详细代码

解法一：

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            return Integer.compare(a[0], b[0]);
        });
        List<int[]> result = new LinkedList<>();
        int start = intervals[0][0];
        int rightEnd = intervals[0][1];

        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] > rightEnd){
                result.add(new int[]{start, rightEnd});
                start = intervals[i][0];
                rightEnd = intervals[i][1];
            }else {
                rightEnd = Math.max(rightEnd, intervals[i][1]);
            }
        }
        result.add(new int[]{start, rightEnd});
        return result.toArray(new int[result.size()][]);
    }
}

解法二：简化写法

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            return Integer.compare(a[0], b[0]);
        });
        LinkedList<int[]> result = new LinkedList<>();
        result.add(intervals[0]);

        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] <= result.getLast()[1]){
                int start = result.getLast()[0];
                int right = Math.max(result.getLast()[1], intervals[i][1]);
                result.removeLast();
                result.add(new int[]{start, right});
            }else{
                result.add(intervals[i]);
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}