区间问题 | LeetCode-56

发表于 2024-09-15 更新于 2024-11-13 分类于算法， LeetCode ，数组阅读次数：阅读次数： Waline：本文字数： 5.5k 阅读时长 ≈ 9 分钟

分类不好，这道题就做不出来！

题目1：452. 用最少数量的箭引爆气球

1.题目描述

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end，且满足 xstart ≤ x ≤ x``end，则该气球会被引爆。可以射出的弓箭的数量 没有限制 。弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数 。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：

1
2
3

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。

提示:

$1 <= points.length <= 10^5$
points[i].length == 2
$-2^{31} <= x_{start} < x_{end} <= 2^{31} - 1$

2.题解

// 解决方案类
class Solution {
    public int findMinArrowShots(int[][] points) {
        // 根据气球直径的开始坐标从小到大排序
        // 使用Integer内置的比较方法，以避免整数溢出问题
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));

        // 初始化箭的数量为1，因为至少需要一支箭
        int result = 1;

        // 遍历气球数组，从第二个气球开始
        for (int i = 1; i < points.length; i++) {
            // 检查当前气球的起始坐标是否大于上一个气球的结束坐标
            if (points[i][0] > points[i - 1][1]) {
                // 当前气球不重叠，需要新的箭
                result++;
            } else {
                // 当前气球与上一个气球重叠，更新当前气球的结束坐标为两者中较小的值
                points[i][1] = Math.min(points[i][1], points[i - 1][1]);
            }
        }

        // 返回最少的箭数量
        return result;
    }
}

题目2：435. 无重叠区间

1.题目描述

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

注意只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。

示例 1:

1
2
3

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

示例 2:

1
2
3

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

1
2
3

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

提示:

$1 <= intervals.length <= 10^5$
intervals[i].length == 2
$-5 * 10^4 <= start_i < end_i <= 5 * 10^4$

2.题解

2.1 贪心算法-写法1

count记录非交叉区间的个数

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // 将区间数组按每个区间的起始位置进行排序
        Arrays.sort(intervals, (a, b) -> {
            return a[0] - b[0]; // 比较两个区间的起始位置，按升序排列
        });
        int count = 1;// 计数器初始化为1，用于统计不重叠的区间数量
        // 遍历区间数组，从第二个区间开始
        for (int i = 1; i < intervals.length; i++) {
            // 如果当前区间与前一个区间不重叠
            if(intervals[i-1][1] <= intervals[i][0]){
                // 增加计数器
                count++;
            } else {
                // 如果当前区间与前一个区间重叠，更新当前区间的右边界为两者右边界的较小值
                intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);
            }
        }
        
        return intervals.length - count;// 返回需要移除的重叠区间数量，即总区间数减去不重叠区间的数量
    }
}

2.2 贪心算法-写法2

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // 将区间数组按每个区间的起始位置进行排序
        Arrays.sort(intervals, (a, b) -> {
            // 比较两个区间的起始位置，按升序排列
            return Integer.compare(a[0], b[0]);
        });

        // 记录需要移除的重叠区间数量
        int remove = 0;
        // 初始化前一个区间的右边界为第一个区间的右边界
        int preR = intervals[0][1];

        // 遍历区间数组，从第二个区间开始
        for (int i = 1; i < intervals.length; i++) {
            // 如果当前区间的起始位置不小于前一个区间的右边界（无重叠）
            if (preR <= intervals[i][0]) {
                // 更新前一个区间的右边界为当前区间的右边界
                preR = intervals[i][1];
            } else {
                // 如果当前区间与前一个区间重叠，增加需要移除的区间计数
                remove++;
                // 更新前一个区间的右边界为两者右边界的较小值，以减少后续重叠
                preR = Math.min(preR, intervals[i][1]);
            }
        }

        // 返回需要移除的重叠区间数量
        return remove;
    }
}

题目3：763. 划分字母区间

1.题目描述

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

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

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

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

示例 2：

1 2	输入：s = "eccbbbbdec" 输出：[10]

提示：

1 <= s.length <= 500
s 仅由小写英文字母组成

2.题解

思路：
- 统计每一个字符最后出现的位置
- 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

class Solution {
    // 定义一个方法 partitionLabels，接收一个字符串 s，返回一个整数列表
    public List<Integer> partitionLabels(String s) {
        // 创建一个长度为26的数组 edge，用于存储每个字符最后出现的位置
        int[] edge = new int[26];
        // 遍历字符串，记录每个字符的最右边界索引
        for(int i = 0; i < s.length(); i++) edge[s.charAt(i) - 'a'] = i;
        // 创建一个结果列表，用于存储每个分区的长度
        List<Integer> result = new ArrayList<>();
        // 初始化两个指针，left 表示分区的起始位置，right 表示当前分区的结束位置
        int left = 0, right = 0;
        // 遍历字符串
        for(int i = 0; i < s.length(); i++) {
            // 更新当前分区的最右边界
            right = Math.max(right, edge[s.charAt(i) - 'a']);
            
            // 如果当前位置 i 等于当前分区的最右边界
            if(right == i) {
                // 将当前分区的长度添加到结果列表中
                result.add(right - left + 1);
                // 更新左边界为下一个分区的起始位置
                left = right + 1;
            }
        }
        return result;
    }
}

题目4：56. 合并区间

1.题目描述

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

示例 1：

1
2
3

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

示例 2：

1
2
3

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

$1 <= intervals.length <= 10^4$
intervals[i].length == 2
$0 <= start_i <= end_i <= 10^4$

2.题解

class Solution {
    public int[][] merge(int[][] intervals) {
        // 如果区间数组为空，直接返回空数组
        if(intervals.length == 0) return new int[0][2];

        // 将区间数组按每个区间的起始位置进行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] intervals1, int[] intervals2) {
                // 按照区间的起始值升序排列
                return intervals1[0] - intervals2[0];
            }
        });

        // 用来保存合并后的区间
        List<int[]> result = new ArrayList<>();

        // 遍历所有区间
        for(int i = 0; i < intervals.length; i++) {
            // 当前区间的左边界 L 和右边界 R
            int L = intervals[i][0], R = intervals[i][1];

            // 如果 result 为空，或者 result 中最后一个区间的右边界小于当前区间的左边界
            // 说明当前区间与前一个区间没有重叠，直接添加当前区间
            if(result.size() == 0 || result.get(result.size() - 1)[1] < L) {
                result.add(new int[]{L, R});
            } else {
                // 否则，说明当前区间和前一个区间有重叠
                // 将最后一个区间的右边界更新为两个区间中较大的右边界，合并区间
                result.get(result.size() - 1)[1] = Math.max(result.get(result.size() - 1)[1], R);
            }
        }

        // 将结果列表转换为二维数组形式并返回
        return result.toArray(new int[result.size()][]);
    }
}

-------------本文结束感谢您的阅读-------------