代码随想录算法训练营第三十天|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]。
提示:
1 <= points.length <= 105points[i].length == 2-231 <= xstart < xend <= 231 - 1
思路：
-
排序: 首先将气球的数组
points按照气球的结束位置（xend）进行升序排序。这样做是因为贪心策略通常希望每次尽可能少地消耗资源（在这里是尽量少发射箭），所以我们优先考虑结束位置较小的气球。 -
贪心选择: 我们从左到右遍历排序后的气球列表，每当我们找到一个新的气球无法被当前箭引爆时（即当前气球的开始位置大于上一个箭的射出位置），我们就需要发射一支新的箭。新的箭的射出位置应该是当前气球的结束位置。
-
更新和计数: 每次发射箭后，更新箭的射出位置，并增加箭的数量。
上代码：
class Solution {
public:int findMinArrowShots(vector<vector<int>>& points) {// 按照气球的结束位置排序sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {return a[1] < b[1];});int arrows = 1; // 至少需要一支箭int end = points[0][1]; // 第一支箭的射出位置for (int i = 1; i < points.size(); ++i) {// 如果当前气球的开始位置大于上一支箭的射出位置if (points[i][0] > end) {++arrows; // 需要一支新的箭end = points[i][1]; // 更新射出位置为当前气球的结束位置}}return arrows;}
};
435. 无重叠区间
题目：
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
示例 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 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
提示:
1 <= intervals.length <= 105intervals[i].length == 2-5 * 104 <= starti < endi <= 5 * 104
思路：
这个问题可以通过贪心算法来解决。
贪心策略的核心是尽可能保留区间的右边界小的区间，因为这样可以留下更多空间给后续区间，从而减少重叠的可能性。
贪心思路
-
排序: 先将区间按照结束时间（
endi）进行升序排序。结束时间越早的区间，留给后续区间的空间就越多，因此我们优先考虑这些区间。 -
选择区间: 遍历排序后的区间集合，并逐一选择不与前一个已选择区间重叠的区间。如果当前区间的开始时间大于等于前一个区间的结束时间，则它们不重叠，保留当前区间；否则，当前区间需要被移除。
-
计数: 记录需要移除的区间数量，即无法与前一个区间兼容的区间数。
上代码：
class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.empty()) return 0;// 按照区间的结束时间排序sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {return a[1] < b[1];});int count = 0; // 需要移除的区间数int end = intervals[0][1]; // 第一个区间的结束时间for (int i = 1; i < intervals.size(); ++i) {if (intervals[i][0] < end) {// 当前区间与前一个区间重叠，移除当前区间++count;} else {// 不重叠，更新end为当前区间的结束时间end = intervals[i][1];}}return count;}
};
763.划分字母区间
题目：
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：输入：s = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = "eccbbbbdec" 输出：[10]
提示：
1 <= s.length <= 500s仅由小写英文字母组成
思路：
这个问题可以通过贪心算法来解决。
贪心策略的核心是尽可能扩展当前片段，使得该片段包含该片段内所有字符的最后出现位置。
这样，我们可以保证同一个字符不会出现在多个片段中。
贪心思路
-
记录字符最后出现的位置: 首先，遍历字符串
s，记录每个字符最后出现的位置。这一步可以通过一个哈希表或者数组来实现。 -
划分片段: 再次遍历字符串，维护当前片段的起始位置
start和结束位置end。对于当前遍历到的字符，如果它的最后出现位置大于当前end，则更新end为该字符的最后出现位置。当遍历到end时，说明当前片段已经形成，可以记录下片段长度，并更新start为下一个片段的起始位置。 -
存储结果: 将每个片段的长度存储到结果列表中，最后返回该列表。
上代码：
class Solution {
public:vector<int> partitionLabels(string s) {vector<int> last(26, 0); // 记录每个字符最后出现的位置// 先遍历字符串，记录每个字符的最后出现位置for (int i = 0; i < s.size(); ++i) {last[s[i] - 'a'] = i;}vector<int> result; // 存储每个片段的长度int start = 0, end = 0;// 再次遍历字符串，划分片段for (int i = 0; i < s.size(); ++i) {end = max(end, last[s[i] - 'a']); // 更新当前片段的结束位置// 当遍历到片段的结束位置时，记录片段长度if (i == end) {result.push_back(end - start + 1);start = i + 1; // 更新下一个片段的起始位置}}return result;}
};