怎么让百度收录网站_菜单制作软件app_怎么利用互联网推广_重庆森林经典台词 凤梨罐头

---

56. 合并区间

• 题目链接：56. 合并区间
• 讲解链接：代码随想录
• 状态：直接看题解了。

思路与重点

• 如何去模拟合并区间呢？其实就是用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。
• 注意lambda表达式的用法，可以简化代码！

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if (intervals.size() == 0) return result; // 区间集合为空直接返回// 排序的参数使用了lambda表达式sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});// 第一个区间就可以放进结果集里，后面如果重叠，在result上直接合并result.push_back(intervals[0]); for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间// 合并区间，只更新右边界就好，因为result.back()的左边界一定是最小值，因为我们按照左边界排序的result.back()[1] = max(result.back()[1], intervals[i][1]); } else {result.push_back(intervals[i]); // 区间不重叠 }}return result;}
};

738.单调递增的数字

• 题目链接：738.单调递增的数字
• 讲解链接：代码随想录
• 状态：直接看题解了。

思路与重点

• 本题只要想清楚个例，例如98，**一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]减一，strNum[i]赋值9，这样这个整数就是89。**就可以很自然想到对应的贪心解法了。
• 想到了贪心，还要考虑遍历顺序，只有从后向前遍历才能重复利用上次比较的结果。
• 最后代码实现的时候，也需要一些技巧，例如用一个flag来标记从哪里开始赋值9。

class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b){return a[0] < b[0];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);int ans = 0;for(int i = 1; i < intervals.size(); i++){if(intervals[i][0] < intervals[i-1][1]){ans++;intervals[i][1] = min(intervals[i][1], intervals[i-1][1]);}}return ans;}
};

968.监控二叉树

• 题目链接：968.监控二叉树
• 讲解链接：代码随想录
• 状态：直接看题解了。

思路与重点

• 我们要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！
• 大体思路就是从下往上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。
• 如何隔两个节点放一个摄像头：此时需要状态转移的公式，大家不要和动态的状态转移公式混到一起，本题状态转移没有择优的过程，就是单纯的状态转移！来看看这个状态应该如何转移，先来看看每个节点可能有几种状态：
  • 0：该节点无覆盖
  • 1：本节点有摄像头
  • 2：本节点有覆盖

class Solution {
private:int result;int traversal(TreeNode* cur) {if (cur == NULL) return 2;int left = traversal(cur->left);    // 左int right = traversal(cur->right);  // 右if (left == 2 && right == 2) return 0;else if (left == 0 || right == 0) {result++;return 1;} else return 2;}
public:int minCameraCover(TreeNode* root) {result = 0;if (traversal(root) == 0) { // root 无覆盖result++;}return result;}
};

贪心算法总结

• 代码随想录