文章目录
- 一、Leetcode 452.用最少数量的箭引爆气球
- 二、Leetcode 435.无重叠区间
- 三、Leetcode 763.划分字母区间
一、Leetcode 452.用最少数量的箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中 points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend 之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
示例：
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。
引用：
原文链接：https://programmercarl.com/0452.%E7%94%A8%E6%9C%80%E5%B0%91%E6%95%B0%E9%87%8F%E7%9A%84%E7%AE%AD%E5%BC%95%E7%88%86%E6%B0%94%E7%90%83.html
题目链接：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/
视频讲解：https://www.bilibili.com/video/BV1SA41167xe/
当两个气球的大小有重叠的部分时，我们就可以只使用一只箭来射击。
贪心思想：
局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。
所以我们先对这些气球进行排序，按照左区间的大小来排序，方便我们后续计算。
两种情况：
- 当前气球的左区间大于前一个气球的右区间时，说明两个区间没有重叠的部分，这时就需要多加一只箭了。
- 当前气球的左区间小于等于前一个气球的右区间时，说明两个区间有重叠的部分，这时两个气球可以一只箭来射击，我们需要将当前气球的右区间更新为当前气球的右区间和前一个气球的右区间的最小值。 这样我们才能判断两个以上气球重叠的情况。
代码：
class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:if len(points) == 0:return 0points.sort(key=lambda x:x[0])result = 1for i in range(1, len(points)):if points[i][0] > points[i-1][1]:result += 1else:points[i][1] = min(points[i-1][1], points[i][1])return result
二、Leetcode 435.无重叠区间
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3]是不重叠的。
示例：
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
引用
原文链接：https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html
题目链接：https://leetcode.cn/problems/non-overlapping-intervals/description/
视频讲解：https://www.bilibili.com/video/BV1A14y1c7E1/
本体和上一道题射气球非常类似。
需要删除的区间，实际上就是判断有多少区间重合。
之后的操作和上一题完全一样。
代码：
class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:intervals.sort(key=lambda x:x[0])result = 0if not intervals: return resultfor i in range(1, len(intervals)):if intervals[i][0]<intervals[i-1][1]:result += 1intervals[i][1] = min(intervals[i][1], intervals[i-1][1])return result
三、Leetcode 763.划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例：
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
引用：
原文链接：https://programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html
题目链接：https://leetcode.cn/problems/partition-labels/description/
视频讲解：https://www.bilibili.com/video/BV18G4y1K7d5/
在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。
可以分为如下两步：
- 统计每一个字符最后出现的位置
- 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点。
统计完字符后，我们定义两个指针 left 和 right，初始化为零，用于分割字符串。
循环过程中，我们都要将 right 更新为字符出现过的最远位置，只有当 i 遍历到 right 的时候，我们才包含了所有可能出现的字符，并且下一个区间不会再包含重复的字符。然后保存结果，再更新左边界 left ，开始记录下一个区间。
代码：
class Solution:def partitionLabels(self, s: str) -> List[int]:table = {}for i in range(len(s)):table[s[i]] = iresult = []left = 0right = 0for i in range(len(s)):right = max(table[s[i]], right)if i==right:result.append(right-left+1)left = i + 1return result