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

本文主要是介绍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 = 0n = len(nums)while i < n:low = ii += 1while i < n and nums[i] == nums[i-1]+1: # 连续的有序区间i += 1high = i-1region = 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 = Trueans.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] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

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

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

题目归纳：

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

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:# 第一种解法还用到了burst数组，这里的解法利用数组的有序特性，一次遍历即可if not points:return 0points.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 += 1pos = points[i][1]  # 瞄准该气球的右端点return ans

这篇关于Leetcod面试经典150题刷题记录 —— 区间篇的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---