代码随想录算法训练营第三十天 | 452.用最少数量的箭引爆气球 435.无重叠区间 763.划分字母区间

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

文章链接
题目链接：452.用最少数量的箭引爆气球

思路：

气球的区间有重叠部分，只要弓箭从重叠部分射出来，那么就能减少所使用的弓箭数
**局部最优：**只要有重叠部分，就从重叠部分射出弓箭
全局最优：引爆所有气球所必须射出的最小弓箭数。

① 要求重叠部分最好先将points数组排序，按start或end都可以，此处按照start顺序排序。
② 因为只需要弓箭的数目，因此不需要记录有哪些重叠区间，只需要变量minRight记录重叠气球最小右边界和count记录弓箭数即可。

③ 从前向后遍历，如果当前气球与之前气球区间有重叠部分，即points[i][0] <= minRight，那么更新minRight；如果没有重叠部分，重置minRight为points[i][1]重新记录重叠气球最小右边界，并增加一支弓箭

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:if len(points) <= 0:return 0points.sort(key=lambda x: x[0])count = 1   # points不为空，至少需要一支箭minRight = points[0][1] # 记录最小右边界，因为有重叠部分右边界只会减小for point in points:if point[0] > minRight: # 没挨着minRight = point[1]    # 重置minRightcount += 1  # 增加一支箭else:minRight = min(minRight, point[1])  # 得到最小右边界return count"""
不使用minRight记录，使用points[i - 1][1]记录最小右边界
"""
class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:if len(points) <= 0:return 0points.sort(key=lambda x: x[0]) # 排序count = 1   # points不为空至少需要一支弓箭for i in range(1, len(points)):if points[i][0] > points[i - 1][1]: # 当前气球区间与前一个没有挨着count += 1else:points[i][1] = min(points[i - 1][1], points[i][1])  # 更新最小右边界return count

感悟：

只记录数量的话，函数实现过程中不用记录所有重叠区间，使用一个变量记录当前重叠气球最小右边界即可（因为排序后如果当前气球与前面不重叠的话，原来的重叠气球部分与之后的不会重叠了，那么就只需要记录新的即可）

---

LeetCode 435.无重叠区间：

文章链接
题目链接：435.无重叠区间

思路:

一般来说，多个区间重叠有两种情况：以三个区间重叠为例
1）第三个区间的重叠部分在前两个区间的重叠部分中。
那么需要删除其中两个区间才能使区间不重叠

2）第三个区间的重叠部分不在前两个区间的重叠部分中。
那么只需要删除中间的区间就能使得两个区间不重叠。

如果采用的是两个区间重叠后保留的是重叠部分，再与后面的区间进行判断是否重叠，那么可以统一上面两种情况（第二种情况到第三个区间时会判断不重叠）。

1. 记录重叠部分
   那么我们首先对区间集合按照左边界进行排序，同时使用minRight记录重叠区间的最小右边界，count记录重叠区间数。

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:if len(intervals) <= 0:return 0intervals.sort(key=lambda x: x[0])count = 0   # 记录重叠的区间数minRight = intervals[0][1]for i in range(1, len(intervals)):if intervals[i][0] >= minRight:minRight = intervals[i][1]else:count += 1minRight = min(minRight, intervals[i][1])return count

2. 记录不重叠部分
   其实记录不重叠部分可以对上面的代码进行修改，count += 1从else改成if， 同时初始化为1即可。
   还有一种方法，因为判断是否重叠采用的是重叠部分最小右边界，因此是否可以直接对数组按照右边界进行排序，如果后面的区间与前面不重叠，重置最小右边界；否则不进行操作（因为按照右边界排序，前面重叠部分第一个一定是最小右边界）

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:if len(intervals) <= 0:return 0intervals.sort(key=lambda x:x[1])   # 按右边界进行排序count = 1   # 记录非重叠区间数minRight = intervals[0][1]for i in range(1, len(intervals)):if intervals[i][0] >= minRight:	# 不重叠count += 1minRight = intervals[i][1]return len(intervals) - count

感悟：

判断是否重叠采用的是重叠最小右边界，n个区间是否重叠是看前面n - 1个的重叠部分是否在第n个区间中出现（即上图情况1）。使用最小右边界进行判断，可以直接对数组按照右边界进行排序，从而只需要在不重叠时重置minRight即可。

---

LeetCode 763.划分字母区间：

文章链接
题目链接：763.划分字母区间

思路：

1. 贪心1（可能不算贪心）
   ① 首先求出字符串中每个字符的最远位置（用数组）
   ② 遍历字符串，同时更新当前遍历片段的最远位置（即其中字符最远位置的最远位置），如果当前位置为最远位置，表明到达切分点，对字符串进行切分后继续遍历下一片段

class Solution:def partitionLabels(self, s: str) -> List[int]:if len(s) <= 0:return []hashLetter = [-1] * 26  # 保存字符的最远下标for i in range(len(s)):hashLetter[ord(s[i]) - ord('a')] = iresult = []start = 0   # 当前片段开始maxIndex = 0 # 当前片段中字符中最远位置的最远位置，即当前片段结束for i in range(len(s)):# 更新最远位置if hashLetter[ord(s[i]) - ord('a')] > maxIndex:maxIndex = hashLetter[ord(s[i]) - ord('a')]if maxIndex == i:    # 到达最远位置即片段结束result.append(i - start + 1)    # 双闭区间# 重置start等为下一个片段start = i + 1maxIndex = 0return result

2. 贪心2
   类似前面引爆气球和无重叠区间的思路。
   ① 记录字符串中每个字符的开始位置和结束位置，从而得到一系列区间
   ② 首先对区间按照左边界进行排序，然后对重叠的区间进行合并，此处判断多个区间是否重叠包含如下两种情况
   1）第三个区间的重叠部分在前两个区间的重叠部分中。
   
   2）第三个区间的重叠部分不在前两个区间的重叠部分中。
   
   ③ 从而使用最大右边界记录当前重叠区间的右边界。如果下一个区间没有和当前区间重叠，说明重叠结束，应当划分片段。
   需要注意的是：
   1）记录字符的开始和结束位置，记录开始位置的同时要记录结束位置（因为会出现字符只出现一次的情况）
   2）前面记录字符的开始和结束采用的是数组，字符到数组下标的映射为ord(x) - ord(‘a’)，因此在排序区间数组前需要清理掉字符串中没有用到的字符。
   3）前面几题只需要记录数量，此处需要划分区间，因此需要start记录区间的开始
   4）for循环遍历完成后，还有最后一个区间没有加入result中

class Solution:def countLetter(self, s):# 记录字符串中每个字符的开始和结束位置letterSE = [[-1, -1] for _ in range(26)]for i in range(len(s)):if letterSE[ord(s[i]) - ord('a')][0] == -1:letterSE[ord(s[i]) - ord('a')][0] = iletterSE[ord(s[i]) - ord('a')][1] = i# 去除letterSE的s不存在的字符letters = []for i in range(len(letterSE)):if letterSE[i][0] != -1:letters.append(letterSE[i])return lettersdef partitionLabels(self, s: str) -> List[int]:if len(s) <= 0:return 0letters = self.countLetter(s)   # 得到各个字符的区间letters.sort(key=lambda x: x[0])    # 按照左边界排序# 字符串中多个字符重叠区间的最大值即为所划分区间result = []start = 0maxRight = letters[0][1]    # 这里是求最大右边界for i in range(1, len(letters)):if letters[i][0] > maxRight:    # 没挨着result.append(maxRight - start + 1)start = letters[i][0]maxRight = max(letters[i][1], maxRight)# 结尾一个result.append(maxRight - start + 1)return result

---

学习收获：

区间是否重叠，以及如何求存在重叠部分的重叠区间数和非重叠区间数，以及合并区间