【LeetCode】区间（合并、插入、重叠区间、最小区间······）

落日映苍穹つ 2023-01-06 15:52 271阅读 0赞

文章目录

      • 汇总区间★
      • 无重叠区间★★
      • 合并区间★★
      • 插入区间★★★
      • 最小区间★★★
      • 区间和的个数★★★

汇总区间★

LeetCode228. 汇总区间

【题目】给定一个无重复元素的有序整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

  • “a->b” ，如果 a != b
  • “a” ，如果 a == b

【示例】

  1. 输入：nums = [0,2,3,4,6,8,9]
  2. 输出：["0","2->4","6","8->9"]
  3. 解释：区间范围是：
  4. [0,0] --> "0"
  5. [2,4] --> "2->4"
  6. [6,6] --> "6"
  7. [8,9] --> "8->9"

【解题思路】

  • 无连续的数字单独作为区间

  • 有连续数字取区间两端

    class Solution {

    1. public List<String> summaryRanges(int[] nums) {
    3.     List<String> list = new ArrayList<>();
    4.     for(int i = 0; i < nums.length; i++) {
    6.         StringBuffer sb = new StringBuffer();
    7.         sb.append(nums[i]);
    8.         if(i + 1 < nums.length && nums[i + 1] - nums[i] == 1) {
    10.             int j = i + 1;
    11.             while(j + 1 < nums.length && nums[j + 1] - nums[j] == 1) {
    13.                 j++;
    14.             }
    15.             i = j;
    16.             sb.append("->");
    17.             sb.append(nums[j]);
    18.         }
    19.         list.add(sb.toString());
    20.     }
    21.     return list;
    22. }

    }

无重叠区间★★

LeetCode435. 无重叠区间

【题目】给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

  • 可以认为区间的终点总是大于它的起点。
  • 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

【示例】

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

【解题思路】贪心法

方法一：按左端点排序

  1. class Solution {
  3.     public int eraseOverlapIntervals(int[][] intervals) {
  5.         if(intervals == null || intervals.length == 0) return 0;
  6.         Arrays.sort(intervals, (o1, o2) -> (o1[0] - o2[0]));
  7.         int count = 0;    //记录移除区间个数
  8.         int end = intervals[0][1];   //记录区间右端
  9.         for(int i = 1; i < intervals.length; i++) {
  11.             if(intervals[i][0] < end) {
  13.                 count++;
  14.                 //取右端比较小的，这样才能容纳更多的区间
  15.                 end = Math.min(end, intervals[i][1]);
  16.             }else {
  18.                 end = intervals[i][1];
  19.             }
  20.         }
  21.         return count;
  22.     }
  23. }

方法二：按右端点排序

  1. class Solution {
  3.     public int eraseOverlapIntervals(int[][] intervals) {
  5.         if(intervals == null || intervals.length == 0) return 0;
  6.         Arrays.sort(intervals, (o1, o2) -> (o1[1] - o2[1]));
  7.         int count = 0;    //记录移除区间数
  8.         int end = intervals[0][1];  //记录区间最右端
  9.         for(int i = 1; i < intervals.length; i++) {
  11.             if(intervals[i][0] < end) {
  13.                 count++;
  14.             }else {
  16.                 end = intervals[i][1];
  17.             }
  18.         }
  19.         return count;
  20.     }
  21. }

合并区间★★

LeetCode 56. 合并区间

【题目】给出一个区间的集合，请合并所有重叠的区间。

【示例】

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

【解题思路】

方法一：自定义排序

先按照左端点排序，之后顺序遍历，若左右元素相交，则更新区间大小，否则加入区间结果集

  1. class Solution {
  3.     public int[][] merge(int[][] intervals) {
  5.         if(intervals == null || intervals.length == 0) return new int[][]{
  6.     {
  7.     }};
  8.         Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
  9.         List<int[]> list = new ArrayList<int[]>();
  10.         int le = intervals[0][0], ri = intervals[0][1];
  11.         for(int i = 1; i < intervals.length; i++) {
  13.             if(intervals[i][0] > ri) {
  15.                 list.add(new int[]{
  16.     le, ri});
  17.                 le = intervals[i][0];
  18.                 ri = intervals[i][1];
  19.             }else {
  21.                 ri = Math.max(ri, intervals[i][1]);
  22.             }
  23.         }
  24.         list.add(new int[]{
  25.     le, ri});
  26.         return list.toArray(new int[list.size()][2]);
  27.     }
  28. }

方法二：位图

使用BitSet模拟坐标轴

  1. class Solution {
  3.     public int[][] merge(int[][] intervals) {
  5.         BitSet bitSet = new BitSet();
  6.         int max = 0;
  7.         for(int[] e : intervals) {
  9.             int t = e[1] * 2 + 1;    //乘以2是为了标记类似[a, a]的区间
  10.             bitSet.set(e[0] * 2 , t, true);
  11.             max = Math.max(max, t);
  12.         }
  13.         List<int[]> list = new ArrayList<int[]>();
  14.         int index = 0;
  15.         while(index < max) {
  17.             int start = bitSet.nextSetBit(index);
  18.             int end = bitSet.nextClearBit(start);
  19.             list.add(new int[]{
  20.     start / 2, (end - 1) / 2});
  21.             index = end;
  22.         }
  23.         return list.toArray(new int[list.size()][]);
  24.     }
  25. }

插入区间★★★

LeetCode 57. 插入区间

【题目】给出一个*无重叠的 ，*按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

【示例】

  1. 输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
  2. 输出：[[1,2],[3,10],[12,16]]
  3. 解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠

【解题思路】

分三步走：

  • 小于插入区间左端点的不用合并
  • 合并区间时，左端点取最小值，右端点取最大值

  • 大于插入区间右端点的不用合并

    class Solution {

    1. public int[][] insert(int[][] intervals, int[] newInterval) {
    3.     int t = 0;
    4.     List<int[]> list = new ArrayList<int[]>();
    6.     //小于newInterval[0](左端点)的不用合并
    7.     while(t < intervals.length && intervals[t][1] < newInterval[0]){
    9.         list.add(intervals[t]);
    10.         ++t;
    11.     }
    13.     //合并区间    左端点取最小，右端点取最大
    14.     while(t < intervals.length && intervals[t][0] <= newInterval[1]){
    16.         newInterval[0] = Math.min(newInterval[0], intervals[t][0]);
    17.         newInterval[1] = Math.max(newInterval[1], intervals[t][1]);
    18.         ++t;
    19.     }
    20.     list.add(newInterval);
    22.     //大于newInterval[1](右端点)的不用合并
    23.     while(t < intervals.length){
    25.         list.add(intervals[t]);
    26.         ++t;
    27.     }
    28.     return list.toArray(new int[0][]);
    29. }

    }

最小区间★★★

LeetCode 632. 最小区间

【题目】你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

提示：

  • nums.length == k
  • 1 <= k <= 3500
  • 1 <= nums[i].length <= 50
  • -105 <= nums[i][j] <= 105
  • nums[i] 按非递减顺序排列

【示例】

  1. 输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
  2. 输出：[20,24]
  3. 解释： 
  4. 列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
  5. 列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
  6. 列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

【解题思路】

滑动窗口

将每个列表中的数字与其列表位置映射为二维数组，并按大小排序，

接着若滑动窗口中包含每个分组中的数，就可以更新结果了

  1. class Solution {
  3.     public int[] smallestRange(List<List<Integer>> nums) {
  5.         int N = 0;
  6.         for(List<Integer> num : nums) N += num.size();
  8.         //将列表映射为一个二维数组{值， 分组}
  9.         int[][] help = new int[N][2];
  10.         int k = 0;
  11.         for(int i = 0; i < nums.size(); i++) {
  13.             List<Integer> num = nums.get(i);
  14.             for(int j = 0; j < num.size(); j++) {
  16.                 help[k][0] = num.get(j);
  17.                 help[k][1] = i;
  18.                 k++;
  19.             }
  20.         }
  22.         Arrays.sort(help, (o1, o2) -> o1[0] - o2[0]);
  24.         int[] res = {
  25.     0, 0};
  26.         int[] group = new int[nums.size()];
  27.         int count = 0;
  28.         k = 0;
  29.         for(int i = 0; i < N; i++) {
  31.             //记录滑动窗口内组数
  32.             if(0 == group[help[i][1]]++) count++;
  33.             if(count == group.length) {
  35.                 //收缩窗口
  36.                 while(group[help[k][1]] > 1) group[help[k++][1]]--;
  37.                 //更新结果
  38.                 if(res[0] == 0 && res[1] == 0 || help[i][0] - help[k][0] < res[1] - res[0]) {
  40.                     res[0] = help[k][0];
  41.                     res[1] = help[i][0];
  42.                 }
  43.             }
  44.         }
  46.         return res;
  48.     }
  49. }

区间和的个数★★★

LeetCode 327. 区间和的个数

【题目】给定一个整数数组 nums，返回区间和在 [lower, upper] 之间的个数，包含 lower 和 upper。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

说明:
最直观的算法复杂度是 O(n^2) ，请在此基础上优化你的算法。

【示例】

  1. 输入: nums = [-2,5,-1], lower = -2, upper = 2,
  2. 输出: 3 
  3. 解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: -2, -1, 2。

【解题思路】

方法一：暴力法

  1. class Solution {
  3.     public int countRangeSum(int[] nums, int lower, int upper) {
  5.         int count = 0;
  6.         for(int i = 0; i < nums.length; i++){
  8.             long sum = 0;
  9.             for(int j = i; j < nums.length; j++){
  11.                 sum += nums[j];
  12.                 if(sum >= lower && sum <= upper){
  14.                     count++;
  15.                 }
  16.             }
  17.         }
  18.         return count;
  19.     }
  20. }

方法二：归并排序思想

解题方法来自官方题解
https://leetcode-cn.com/problems/count-of-range-sum/solution/qu-jian-he-de-ge-shu-by-leetcode-solution/

具体思路如下图所示

在这里插入图片描述

  1. class Solution {
  3.     //归并复制辅助数组
  4.     private static long[] aux;
  6.     public int countRangeSum(int[] nums, int lower, int upper) {
  8.         if(nums == null || nums.length == 0) return 0;
  9.         aux = new long[nums.length + 1];
  11.         //前缀和数组
  12.         long[] pre = new long[nums.length + 1];
  13.         for(int i = 0; i < nums.length; i++) {
  15.             pre[i + 1] = pre[i] + nums[i];
  16.         }
  18.         return sort(pre, 0, pre.length - 1, lower, upper);
  19.     }
  21.     private int sort(long[] pre, int le, int ri, int lower, int upper) {
  23.         if(le >= ri) return 0;
  24.         int mid = le + (ri - le) / 2;
  25.         int countleft  = sort(pre, le, mid, lower, upper);
  26.         int countright = sort(pre, mid + 1, ri, lower, upper);
  27.         int countcur = merge(pre, le, mid, ri, lower, upper);
  28.         return countleft + countright + countcur;
  29.     }
  31.     private int merge(long[] pre, int le, int mid, int ri, int lower, int upper) {
  33.         //复制
  34.         for(int k = le; k <= ri; k++) {
  36.             aux[k] = pre[k];
  37.         }
  39.         //计算符合要求的区间和个数
  40.         int count = 0;
  41.         int k = le, i = mid + 1, j = mid + 1;
  42.         while(k <= mid) {
  44.             while(i <= ri && pre[i] - pre[k] < lower)  i++;
  45.             while(j <= ri && pre[j] - pre[k] <= upper) j++;
  46.             count += j - i;
  47.             k++;
  48.         }
  50.         //合并
  51.         k = le;
  52.         i = le;
  53.         j = mid + 1;
  54.         while(i <= mid || j <= ri) {
  56.             if(i > mid) {
  58.                 pre[k++] = aux[j++];
  59.             }else if(j > ri) {
  61.                 pre[k++] = aux[i++];
  62.             }else if(aux[i] <= aux[j]){
  64.                 pre[k++] = aux[i++];
  65.             }else {
  67.                 pre[k++] = aux[j++];
  68.             }
  69.         }
  71.         return count;
  72.     }
  73. }

发表评论

表情：
评论列表 （有 0 条评论，271人围观）

还没有评论，来说两句吧...

相关阅读

    相关 leetcode 重叠区间问题

    重叠区间问题可以总结为在坐标轴上若干个位置为 (start(i),end(i))的区间，要求求解这些区间中有多少个不重叠区间，或者合并重叠的区间。 leetcode有大神总结

    向右看齐向右看齐/ 0 赞/ 458 阅读