Leetcod面试经典150题刷题记录 —— 区间篇

2023-12-27 16:30:46

Leetcod面试经典150题刷题记录 —— 区间篇

1. 汇总区间

题目链接:汇总区间 - leetcode
题目描述:
给定一个 无重复元素 的 有序 整数数组 nums 。返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说,nums 的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums 的数字 x 。列表中的每个区间范围 [a,b] 应该按如下格式输出:
"a->b" ,如果 a != b
"a" ,如果 a == b

示例 1:
输入:nums = [0,1,2,4,5,7]
输出:[“0->2”,“4->5”,“7”]
解释:区间范围是:
[0,2] --> “0->2”
[4,5] --> “4->5”
[7,7] --> “7”
示例 2:
输入:nums = [0,2,3,4,6,8,9]
输出:[“0”,“2->4”,“6”,“8->9”]
解释:区间范围是:
[0,0] --> “0”
[2,4] --> “2->4”
[6,6] --> “6”
[8,9] --> “8->9”

题目归纳:

解题思路:
(1) 解法: 汇总区间 - leetcode官方题解

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        # 给定一个整数数组,满足以下性质
        # (1)无重复元素
        # (2)有序
        # 请返回 恰好覆盖数组中所有数字 的 最小有序区间范围列表,也就是说,nums的每个元素都恰好被某个区间范围所覆盖,且不存在属于某个范围,但不属于nums的数字x
        # demo1
        # 输入:nums = [0,1,2,4,5,7]
        # 输出:["0->2","4->5","7"]
        # demo2
        # 输入:nums = [0,2,3,4,6,8,9]
        # 输出:["0","2->4","6","8->9"]

        # 理解题意并不困难,这个章节是使用区间来求解题目,那么这道题要如何使用区间呢?
        # 从下标0出发,向右遍历,每次遇到相邻元素差值>1, 即找到了一个区间,遍历完数组后,则能得到一系列区间列表。
        # low记录区间起点,high记录区间终点
        # low < high,字符串表示为"low->high"
        # low = high, 字符串表示为"low"或"high"

        ans = []
        i = 0
        n = len(nums)
        while i < n:
            low = i
            i += 1
            while i < n and nums[i] == nums[i-1]+1: # 连续的有序区间
                i += 1
            
            high = i-1
            region = str(nums[low])
            if low < high:
                region = region + "->"
                region = region + str(nums[high])
            
            ans.append(region)
        return ans

2. 合并区间

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

示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。

题目归纳:
题意理解起来较容易。

解题思路:
解法: 合并区间 - leetcode官方题解

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # 排序法
        # 按区间左端点进行排序,那么在排完序的列表中,可合并的区间一定连续
        # 用数组merged存储最终答案
        # (1)将列表中的区间,按左端点升序排序,然后将第一个区间加入merged数组中,并按顺序依次考虑之后的每个区间
        # (2)若当前区间的左端点,在数组merged中最后一个区间的右断点之后,那么这两个区间不会重合,可直接将该区间加入数组merged的末尾
        #    否则,它们重合,用当前区间的右端点,更行数组merged中最后一个区间的右端点,取二者最大值即max(current_interval_r, last_interval_r)

        intervals.sort(key=lambda x: x[0]) # 以x[0]为排序的关键字

        merged = []
        for interval in intervals:
            # (1)如果merged为空,或,当前区间与merged最后一个区间不重合,可直接添加
            if not merged or merged[-1][1] < interval[0]: # merged[-1][1]最后一个区间的右端点 < 当前区间的左端点
                merged.append(interval)
            else: # (2)可以合并,并更新最后一个区间的右端点
                merged[-1][1] = max(merged[-1][1], interval[1])
        
        return merged

3. 插入区间

题目链接:插入区间 - leetcode
题目描述:
给你一个 无重叠的 ,按照区间起始端点排序的区间列表。在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。
题目归纳:

解题思路:
解法: 插入区间 - leetcode官方题解

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        # 和上一题合并区间一脉相承
        # 题目描述:给一个无重叠的,按区间左端点排序的区间列表,往列表插入一个新区间,需要保证列表中的区间仍然有序且不重叠
        # 算法过程
        # (1)找出所有与区间newInterval重叠的区间,记为X
        # (2)将X中所有区间连带newInterval合并成一个大区间BIG_X
        # (3)最终答案即为:合并后的BIG_X + 不与X重叠的区间

        # 重叠的分类讨论
        # 考虑两个区间:S1=[l1, r1], S2=[l2, r2]
        # 若:
        # r1 < l2 or r2 < l1: 无重叠
        # 不符合(r1 < l2 or r2 < l1): 有重叠

        left, right = newInterval[0], newInterval[1]
        placed = False       # 是否将合并后的区间放入答案
        ans = []
        for li,ri in intervals:
            if ri < left:    # 当前区间在newInterval的左侧
                ans.append([li, ri])
            elif right < li: # 当前区间在newInterval的右侧
                if not placed:
                    ans.append([left, right])
                    placed = True
                ans.append([li, ri])
            else:            # 存在交集,计算区间并集,不会往ans中添加内容
                left = min(left, li)
                right = max(right, ri)

        if not placed:       # 数组为空或合并到区间数组的末尾仍未放置
            ans.append([left, right])
        return ans

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

题目链接:用最少数量的箭引爆气球 - leetcode
题目描述:
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i] = [xstart, xend] 表示水平直径在 xstartxend之间的气球。你不知道气球的确切 y 坐标。

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

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

题目归纳:

解题思路:
解法: 用最少数量的箭引爆气球 - leetcode官方题解
记区间左端点为 x i x_i xi?,右端点为 y i y_i yi?
(1)对数组按区间右端点,升序排序。
(2)每只箭都对准,当前右端点 y i y_i yi?最靠左的气球,即射出位置 p o s = m i n ( y i ) pos = min(y_i) pos=min(yi?)
(3)下一只箭瞄准的气球是,第一个 x i x_i xi?大于上次射出 p o s pos pos的气球,射出位置是该气球的 y i y_i yi?

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        # 第一种解法还用到了burst数组,这里的解法利用数组的有序特性,一次遍历即可
        if not points:
            return 0

        points.sort(key=lambda balloon:balloon[1]) # 按右端点升序排列
        pos = points[0][1]          # 第1个瞄准的气球的右端点
        ans = 1                     # 第1只箭

        for i in range(1, len(points)):
            if points[i][0] > pos : # 找到了下一只箭瞄准的气球
                ans += 1
                pos = points[i][1]  # 瞄准该气球的右端点
        return ans

文章来源:https://blog.csdn.net/weixin_44327736/article/details/135208947
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。