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

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

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

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

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

示例 1：
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
在x = 6处射出箭，击破气球[2,8]和[1,6]。
在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
在x = 2处发射箭，击破气球[1,2]和[2,3]。
在x = 4处射出箭，击破气球[3,4]和[4,5]。

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:points.sort()res = []for i in points:if not res:res.append(i)elif res[-1][1]< i[0]:res.append(i)else:res[-1][0] = i[0]res[-1][1] = min(res[-1][1],i[1])     return len(res)

只需更新重叠区间，如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。

435. 无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。

示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:intervals.sort()res = []for i in intervals:if not res:res.append(i)elif res[-1][1]<= i[0]:res.append(i)else:res[-1][0] = i[0]res[-1][1] = min(res[-1][1],i[1])     return len(intervals) - len(res)

和上题类似，去掉重叠区间后就是不重叠区间。区别是增加了区间端点判别。

763. 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：
输入：s = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的，因为划分的片段数较少。

示例 2：
输入：s = “eccbbbbdec”
输出：[10]

class Solution:def partitionLabels(self, s: str) -> List[int]:res1 = []res2 = []for i in range(len(s)):if s[i] not in res1:res1.append(s[i])res2.append([i,i])else:               res2[res1.index(s[i])][-1]=i result = []for t in res2:if not result:result.append(t)elif result[-1][1]<= t[0]:result.append(t)else:result[-1][1] = max(result[-1][1],t[1])  rr = []for i in result:rr.append(i[1]-i[0]+1)return rr

题目要求将所有划分结果按顺序连接，得到的字符串仍然是 s，所以不能改变相对顺序。先按照字符串顺序返回每个对应字符最小最大索引值。此时题目可转变为不重叠的区间个数，更新每个重叠区间索引后，可得结果。
参考代码思路类似

class Solution:def partitionLabels(self, s: str) -> List[int]:last_occurrence = {}  # 存储每个字符最后出现的位置for i, ch in enumerate(s):last_occurrence[ch] = iresult = []start = 0end = 0for i, ch in enumerate(s):end = max(end, last_occurrence[ch])  # 找到当前字符出现的最远位置if i == end:  # 如果当前位置是最远位置，表示可以分割出一个区间result.append(end - start + 1)start = i + 1return result

class Solution:def countLabels(self, s):# 初始化一个长度为26的区间列表，初始值为负无穷hash = [[float('-inf'), float('-inf')] for _ in range(26)]hash_filter = []for i in range(len(s)):if hash[ord(s[i]) - ord('a')][0] == float('-inf'):hash[ord(s[i]) - ord('a')][0] = ihash[ord(s[i]) - ord('a')][1] = ifor i in range(len(hash)):if hash[i][0] != float('-inf'):hash_filter.append(hash[i])return hash_filterdef partitionLabels(self, s):res = []hash = self.countLabels(s)hash.sort(key=lambda x: x[0])  # 按左边界从小到大排序rightBoard = hash[0][1]  # 记录最大右边界leftBoard = 0for i in range(1, len(hash)):if hash[i][0] > rightBoard:  # 出现分割点res.append(rightBoard - leftBoard + 1)leftBoard = hash[i][0]rightBoard = max(rightBoard, hash[i][1])res.append(rightBoard - leftBoard + 1)  # 最右端return res