LeetCode之区间

228. 汇总区间

class Solution {
    public List<String> summaryRanges(int[] nums) {

        // 输入：nums = [0,1,2,4,5,7] 输出：["0->2","4->5","7"]
        // 创建一个字符串列表，用于存储结果
        List<String> result = new ArrayList<>();
        // 初始化索引i
        int i = 0;

        // 当索引i小于数组长度时，继续循环
        while (i < nums.length) {
            // 记录当前范围的起始索引
            int low = i;
            // 移动到下一个索引
            i++;

            // 检查是否还在连续范围内，nums[i]是否等于前一个数加1
            while (i < nums.length && nums[i] == nums[i - 1] + 1) {
                // 如果是连续的，移动到下一个索引
                i++;
            }

            // 记录当前范围的结束索引
            int high = i - 1;

            // 创建一个字符串缓冲区，存储起始数 
            StringBuilder sb = new StringBuilder(Integer.toString(nums[low]));

            // 如果起始索引低于结束索引，说明是一个范围
            if (low < high) {
                // 添加范围符号
                sb.append("->");
                // 添加结束数
                sb.append(Integer.toString(nums[high]));
            }
            // 将生成的范围或单个数添加到结果列表中
            result.add(sb.toString());
        }
        // 返回结果列表
        return result;
    }

}

56. 合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        // 按照区间的左边界进行升序排序
        Arrays.sort(intervals, (a, b) -> {
            return a[0] - b[0];
        });

        // 创建一个列表用于存储合并后的区间
        List<int[]> merge = new ArrayList<>();

        // 遍历排序后的区间数组
        for (int i = 0; i < intervals.length; i++) {
            // 获取当前区间的左边界
            int left = intervals[i][0];
            // 获取当前区间的右边界
            int right = intervals[i][1];

            // 如果合并列表为空或者当前区间的左边界大于合并列表中最后一个区间的右边界
            // 说明当前区间与之前的区间不重叠，可以直接添加到合并列表中
            if (merge.size() == 0 || merge.get(merge.size() - 1)[1] < left) {
                merge.add(new int[]{left, right});
            } else {
                // 如果当前区间与合并列表中最后一个区间有重叠
                // 则更新合并列表中最后一个区间的右边界为当前区间和合并列表中最后一个区间右边界的较大值
                merge.get(merge.size() - 1)[1] = Math.max(right, merge.get(merge.size() - 1)[1]);
            }
        }

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

57. 插入区间

class Solution {

    public int[][] insert(int[][] intervals, int[] newInterval) {
        // 新插入区间的左边界
        int left = newInterval[0];
        // 新插入区间的右边界
        int right = newInterval[1];

        // 创建一个列表用于存储最终结果
        List<int[]> ansList = new ArrayList<>();

        // 标记新区间是否已被放置
        boolean placed = false;

        // 遍历给定的区间列表
        for (int[] interval : intervals) {
            // 如果当前区间在新插入区间的右侧且无交集
            if (interval[0] > right) {
                // 如果新区间还未被放置，将新区间加入结果列表
                if (!placed) {
                    ansList.add(new int[]{left, right});
                    placed = true;
                }
                // 将当前区间加入结果列表
                ansList.add(interval);
            } else if (interval[1] < left) {
                // 如果当前区间在新插入区间的左侧且无交集，直接将当前区间加入结果列表
                ansList.add(interval);
            } else {
                // 如果当前区间与新插入区间有交集，计算它们的并集
                left = Math.min(interval[0], left);
                right = Math.max(interval[1], right);
            }
        }

        // 如果遍历完所有区间后新区间仍未被放置，将新区间加入结果列表
        if (!placed) {
            ansList.add(new int[]{left, right});
        }

        // 将列表转换为二维数组作为最终结果
        int[][] result = new int[ansList.size()][2];
        for (int i = 0; i < ansList.size(); i++) {
            result[i] = ansList.get(i);
        }
        return result;
    }
}

452. 用最少数量的箭引爆气球

class Solution {
    public int findMinArrowShots(int[][] points) {
        // 对二维数组 points 按照每个区间的右边界进行升序排序
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
        // 初始化第一个区间的右边界为 pre，初始最小箭的数量为 1
        int pre = points[0][1];
        int ans = 1;
        // 遍历所有区间
        for (int[] point : points) {
            // 如果当前区间的左边界大于上一个区间的右边界
            if (point[0] > pre) {
                // 更新 pre 为当前区间的右边界
                pre = point[1];
                // 箭的数量加一
                ans++;
            }
        }
        // 返回最小需要的箭的数量
        return ans;
    }
}