【随想录】Day36—第八章 贪心算法 part05

题目1: 无重叠区间

• 题目链接：435. 无重叠区间

1- 思路

贪心思路：
贪心思路类似于，最少的弓箭射气球的场景

• 通过遍历的方式，遍历区间
• 1. 先根据区间的左侧值对区间进行排序
• 2. 遍历区间
  • **重叠 **：如果当前遍历的区间与前一个区间重叠，此时修改 当前区间的右侧范围 为二者最小值
  • 不重叠：如果此时不重叠，对 res 结果进行 ++。

实际上这个与弓箭射气球所求的结果是相反的，弓箭射气球实际上求的是无重叠区间个数，因此本题目根据弓箭射气球的结果 使用 intervals 的长度减去 无重叠区间个数所得到的就是所求结果：即重叠区间个数。

2- 题解

⭐ 无重叠区间——题解思路

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int res = 1;
        Arrays.sort(intervals,(o1,o2) -> Integer.compare(o1[0],o2[0]));

        for(int i = 1 ; i < intervals.length;i++){
            // 重叠
            if(intervals[i][0] < intervals[i-1][1]){
                intervals[i][1] = Math.min(intervals[i-1][1],intervals[i][1]);
            }else{
                res++;
            }
        }
        return intervals.length - res;
    }
}

题目2: 763. 划分字母区间

• 题目链接：763. 划分字母区间

1- 思路

疑问

• 如何定义一个状态来判断当前字母是否出现过？——> 哈希结构
  • 利用一个数据结构存储字符出现的最远下标位置
• 如何保证当前状态的字母尽可能维持更长？
  • 利用最远下标位置遍历，遍历的过程保证该集合中的下标的最远遍历位置不超过当前字母的最远遍历位置

贪心思路：

• ① 记录每个元素的最远出现位置
  • 定义 int[] hash = new int[26] 哈希数组，从前向后遍历数组，将 hash 数组的值赋值为下标 i。
• ② 遍历字符串，寻找分割点
  • 数据结构：定义 List<Integer> 收集结果
  • 数据结构：定义 left、right 为左右区间指针
  • 右边界取遍历的最大值，如果 **i== right** 证明收集到一个结果，此时收集结果

2- 题解

⭐ 划分字母区间——题解思路

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> partitionLabels(String s) {
        // 遍历 S 初始化 下标数组
        int[] hash = new int[26];
        for(int i = 0 ; i < s.length();i++){
            hash[s.charAt(i)-'a'] = i;
        }
        int left = 0;
        int right = 0;
        for(int i =0  ; i < s.length();i++){
            // 遍历
            right = Math.max(right,hash[s.charAt(i)-'a']);
            // 结果
            if(right==i){
                res.add(right-left+1);
                left = right+1;
            }
        }
        return res;
    }
}

题目3: 56. 合并区间

• 题目链接：56. 合并区间

1- 思路

疑问 && 难点

• 如何记录合并后的区间？ ——> 定义

贪心思路
类似于：弓箭引爆气球

• 1. 对输入的区间根据左侧进行排序
• 2. 遍历排序区间
  • 若重叠：此时更新 right 为最大值
  • 若不重叠：收集结果，更新 left 和 right

2- 题解

⭐ 合并区间——题解思路

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(o1,o2) -> Integer.compare(o1[0],o2[0]));
        List<int[]> res = new ArrayList<>();

        int left = intervals[0][0];
        int right = intervals[0][1];

        for(int i = 1;i < intervals.length;i++){
            // 不重叠，收集结果
            if(intervals[i][0] > right){
                res.add(new int[]{left,right});
                left = intervals[i][0];
                right = intervals[i][1];
            }else{ //重叠：更新最大右边界        
                right = Math.max(right, intervals[i][1]);
            }
        }
        res.add(new int[]{left,right});

        return res.toArray(new int[res.size()][]);
    }
}