代码随想录算法训练营第三十六天|435. 无重叠区间、763.划分字母区间、56. 合并区间

435. 无重叠区间

• 刷题https://leetcode.cn/problems/non-overlapping-intervals/description/
• 文章讲解https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html
• 视频讲解https://www.bilibili.com/video/BV1A14y1c7E1/?vd_source=af4853e80f89e28094a5fe1e220d9062

• 题解：

  class Solution {
      public int eraseOverlapIntervals(int[][] intervals) {
          //这行代码是对一个二维数组intervals进行排序，
          //根据每个子数组的第一个元素进行升序排序。
          //Lambda表达式(a,b)-> { return Integer.compare(a[0],b[0]);} 
          //是用来定义比较规则的，比较的是每个子数组的第一个元素。
          //Arrays.sort方法会根据这个比较规则对intervals进行排序。
          Arrays.sort(intervals, (a, b) -> {
              return Integer.compare(a[0], b[0]);
          });
          int result = 1;
          for(int i = 1; i  
  763.划分字母区间
   
  

  • 刷题https://leetcode.cn/problems/partition-labels/description/
  • 文章讲解https://programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html
  • 视频讲解https://www.bilibili.com/video/BV18G4y1K7d5/?vd_source=af4853e80f89e28094a5fe1e220d9062

  • 题解：

    class Solution {
        public List partitionLabels(String s) {
            List result = new LinkedList();
            //使用类似桶排序的方式，一共有26个英文字母
            int[] edge = new int[26];
            //转化为字符数组
            char[] chars = s.toCharArray();
            //类似桶排序方式，记录当前字母离数组开头的最远的元素的距离
            for(int i = 0; i  
    56. 合并区间
     
    

    • 刷题https://leetcode.cn/problems/merge-intervals/description/
    • 文章讲解https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html
    • 视频讲解https://www.bilibili.com/video/BV1wx4y157nD/?vd_source=af4853e80f89e28094a5fe1e220d9062

    • 题解:

      class Solution {
          public int[][] merge(int[][] intervals) {
              //定义二维数组做结果存储
              List result = new LinkedList();
              //lambda表达式中的比较函数会根据每个区间的第一个元素进行比较
              //从而实现对区间数组的按照第一个元素升序排序。
              Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
              //初始化最小左边界为start
              int start = intervals[0][0];
              int mostRightBound = intervals[0][1];
              for(int i = 1; i  mostRightBound){
                      //加入结果区间并更新start
                      //将一个新的整数数组[start, rightmostRightBound]添加到res中。
                      result.add(new int[]{start, mostRightBound});
                      //并重新更新start,mostRightBound
                      start = intervals[i][0];
                      mostRightBound = intervals[i][1];
                  }else{
                      //当前左边界小于等于最大右边界,则直接在结果集中更新最大右边界
                      mostRightBound = Math.max(mostRightBound, intervals[i][1]);
                  }
              }
              result.add(new int[]{start, mostRightBound});
              return result.toArray(new int[result.size()][]);
          }
      }