跟着Carl学算法--贪心【2】
最少数量箭引爆气球
力扣链接：最少数量箭引爆气球
题目：有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end， 且满足 xstart ≤ x ≤ x``end，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数
思路：
将气球按照右端点排序，每次以气球的右端点射箭，如果下一个气球的左端点小于当前的箭位置，则能顺便射中（因为按照右端点排序的，下一个气球的右端点，一定大于左端点，所以当前箭一定在下一个气球的区间中）
按照气球结束端点排序后
贪心选择：每次选择一个气球的结束坐标（i[1]）作为箭的射击位置。
局部最优：通过选择结束坐标作为射击位置，我们尽可能地让一支箭射爆更多的气球。
因为结束坐标是气球的右边界，所以在这个位置射击，可以保证射爆当前气球，并且尽可能地射爆后续与之重叠的气球。
这种选择在每一步都是局部最优的，因为它最大化了当前箭的利用率。
class Solution {public: int findMinArrowShots(vector<vector<int>>& points) { ranges::sort(points, {}, [](auto& p) { return p[1]; }); // 按照右端点从小到大排序 int count = 0; int cur_point = points[0][1]; for (vector<int> i : points) { if (i[0] > cur_point) { count++; cur_point = i[1]; } } return count; }};无重叠区间
力扣链接：无重叠区间
题目：给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。
思路：
贪心选择是：每次选择结束坐标（p[1]）最小且与当前已选区间不重叠的区间。
局部最优：通过选择结束坐标最小的区间，我们尽可能地为后续区间留下更多的空间。
这样可以保证在每一步选择中，都尽可能地保留更多的区间，从而减少需要移除的区间数量。
这种选择在每一步都是局部最优的，因为它最大化了当前选择的区间数量。
与上一道题，相比所差无几，上一道题也可以看作是求最大无重叠区间数，只有出现下一个区间的左端点，大于当前所记录区间的最右端点时才会计数
区别之处在于，上一题只有端点也不重合才算无重叠，而这一题则是允许端点重叠，即端点重叠也算无重叠区间。
最后所有区间减去最大无重叠区间，即为最小重叠区间
class Solution {public: int eraseOverlapIntervals(vector<vector<int>>& intervals) { ranges::sort(intervals, {}, [](auto& p) { return p[1]; }); int count = 0; int cur_right = INT_MIN; for (auto p : intervals) { if (p[0] >= cur_right) { count++; cur_right=p[1]; } } return intervals.size()- count; }};划分字母区间
力扣链接：划分字母区间
题目：给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 \"ababcc\" 能够被分为 [\"abab\", \"cc\"]，但类似 [\"aba\", \"bcc\"] 或 [\"ab\", \"ab\", \"cc\"] 的划分是非法的。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
思路：
遍历两次字符串，
第一次记录每一个字符最后出现的位置
第二次进行划分
- 每到一个位置，更新其最后结束的位置
- 如果当前位置已经是最后结束位置，则进行一次划分
贪心选择：每次确定一个尽可能小的子串，这个子串包含了在这个子串中出现的所有字母的最后位置。
局部最优：通过每次找到最小的满足条件的子串，我们保证了后续的划分不会受到当前子串的限制。
这样可以保证在每一步选择中，都尽可能地划分出更多的子串。
这种选择在每一步都是局部最优的，因为它最大化了当前步骤可以划分的子串数量。
class Solution {public: vector<int> partitionLabels(string s) { int n = s.size(); int last[26] = {0}; for (int i = 0; i < n; i++) { last[s[i] - \'a\'] = i; } vector<int> result; int end = 0, start = 0; for (int i = 0; i < n; i++) { end = max(end, last[s[i] - \'a\']); if (i == end) { result.push_back(end - start + 1); start = i + 1; } } return result; }};单调递增的数字
力扣链接：单调递增的数字
题目：当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 *小于或等于 n 的最大数字，且数字呈 单调递增。
思路：
贪心策略的核心思想是：
- 从低位到高位，每次只关注相邻的两位数字，如果发现违反单调递增的规则，就立即进行调整。
- 调整的方法是：将高位数字减 1，并将低位数字全部变为 9。
- 这种策略保证了每次调整都是局部最优的，即数字整体是保证遍历过的位数保证递增且小于等于原数字的最大数字
class Solution {public: int monotoneIncreasingDigits(int N) { if (N < 10) // 如果N是个位数，直接返回 return N; for (long long k = 10; N / k > 0; k *= 10) { // 从个位开始，逐渐向高位遍历 if (N / k % 10 > N / (k / 10) % 10) //高位大于低位数字，违反单调递增规则 N -= N % k + 1; // 调整N，使其满足单调递增 } return N; }};监控二叉树
力扣链接： 监控二叉树
**题目：**给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
思路：
代码思路挺简单，需要考虑的情况较多
从下往上遍历（叶子多于根节点，优先叶子处的监控充分利用），叶子结点的上一个为监控，然后依次隔两个放一个监控，
每个结点三种状况，0无覆盖 1监控 2有覆盖
空结点处，设置为有覆盖，不能影响叶子节点的取值
讨论状态迁移
- 当前节点为0，即无覆盖，此时需要左右两个结点均有覆盖
- 当前节点为1，即监控，此时需要左右两个结点至少有一个为无覆盖，这样就可以监控到了
- 当前节点为2，即有覆盖，此时需要左右两个结点至少有一个有监控，监控到此节点，即为有覆盖
最后，因为从下往上放监控，可能出现根节点，无覆盖的情况，所以需要额外判断处理
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), * right(right) {} * }; */// 0无覆盖 1监控 2有覆盖class Solution {public: int minCameraCover(TreeNode* root) { int result = 0;//递归函数，用于返回当前节点的状况 auto dfs = [&](this auto&& dfs, TreeNode* root) -> int { if (!root) return 2; int left = dfs(root->left); int right = dfs(root->right); if (left == 0 || right == 0) { result++; return 1; } if (left == 1 || right == 1) return 2; if (left == 2 && right == 2) return 0; return -1; }; if (dfs(root) == 0) result++; return result; }};
