文章目录
- 题目一：汇总区间
- 题目二：插入区间
语言：python 工具：jupyuter
题目一：汇总区间
给定一个 无重复元素 的 有序 整数数组 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”
前提条件：给定一个无重复元素的有序整数数组 nums 。
期望返回值：返回恰好覆盖数组中所有数字的最小有 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
举例：输入：[0,1,2,4,5,7]
输出：[‘0->2’, ‘4->5’, ‘7’]
因为：0-2连续，4-5连续，7单独，连续的输出为a->b格式，单独的数字就输出a
输入：[0,2,3,4,6,8,9]
输出：[‘0’, ‘2->4’, ‘6’, ‘8->9’]
根据前提条件nums有两种情况：nums为空，nums不为空
如果nums为空，则返回空列表
如果不为空。进入下面算法
python">if not nums:
return []
res = []
当num不为空时，先定义两个指针start和end，表示区间的起始和结束位置，全都初始化为数组的第一个元素。sum[0]sum[0]
python"> start, end = nums[0], nums[0]
接下来开始遍历数组，从数组第二个元素开始如果当前元素与结束位置相邻，则将结束位置向后移动一位，否则将当前区间加入答案，并将起始和结束位置更新为当前位置。
举例：输入：[0,1,2,4,5,7]start和end是0，遍历sum[1]=1=end+1，则将end后移一位变成sum[1],当i=3是，sum[3]!=end+1证明这个递增区间结束了。
python">for i in range(1, len(nums)):
if nums[i] == end + 1:
end = nums[i]
于是把这个区间的开头和结尾按a->b的格式放到res中。
python">res.append(str(start) + "->" + str(end))
当然如果i=6时，这个区间只有一个整数7时，按a的格式放入res中
python">if start == end:
res.append(str(start))
当一个区间结束，应将start和end更新为num[i]num[i]
python">start, end = nums[i], nums[i]
封装以上代码定义一个函数汇总区间函数
python">def summaryRanges(nums):
if not nums:
return []
res = []
start, end = nums[0], nums[0]
for i in range(1, len(nums)):
if nums[i] == end + 1:
end = nums[i]
else:
if start == end:
res.append(str(start))
else:
res.append(str(start) + "->" + str(end))
start, end = nums[i], nums[i]
return res
运行结果：
因为遍历到最后一个元素时，最后一个区间没有被加入答案
python">if start == end:
res.append(str(start))
else:
res.append(str(start) + "->" + str(end))
更新后
python">def summaryRanges(nums):
if not nums:
return []
res = []
start, end = nums[0], nums[0]
for i in range(1, len(nums)):
if nums[i] == end + 1:
end = nums[i]
else:
if start == end:
res.append(str(start))
else:
res.append(str(start) + "->" + str(end))
start, end = nums[i], nums[i]
if start == end:
res.append(str(start))
else:
res.append(str(start) + "->" + str(end))
return res
题目二：插入区间
给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
示例 2：
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
示例 3：
输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]
示例 4：
输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]
示例 5：
输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]
给你一个 无重叠的 ，按照区间起始端点排序的区间列表。在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
段代码首先定义一个空列表 res，用于存储合并后的区间列表。然后，从区间列表的第一个区间开始遍历
python">res=[]
i=0
n=len(intervals)
举例：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
首先[1,3]和[2,5]比较，如果intervals最小的数比newlnterval最大的数小则肯定有重叠给的部分。
因为每个区间都是从小到大，intervals第一个元素是最小，newlnterval最后一个元素最小。
找到重叠部分则合并重叠区间。取intervals和newlnterval中最小元素和最大元素分别做新区间的开头和结尾。并将结果加入res
python">while intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
res.append(newInterval)
如果当intervals最大的数比newlnterval最小的数大，则肯定没重叠部分
如[6,9]和[2,5]，那直接把intervals加入res即可
python">while intervals[i][1] < newInterval[0]:
res.append(intervals[i])
封装插入区间的函数
python">def insert(intervals, newInterval):
res = []
i = 0
n = len(intervals)
while i < n and intervals[i][1] < newInterval[0]:
res.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
res.append(newInterval)
return res
因为遍历到最后一个元素时，最后一个区间没有被加入答案
python">while i < n:
res.append(intervals[i])
更新后
python">def insert(intervals, newInterval):
res = []
i = 0
n = len(intervals)
while i < n and intervals[i][1] < newInterval[0]:
res.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
res.append(newInterval)
while i < n:
res.append(intervals[i])
return res
示例 ：
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
ile i < n:
res.append(intervals[i])
return res
示例 ：
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
