代码随想录算法训练营day31

代码随想录算法训练营

—day31

文章目录

代码随想录算法训练营
前言
一、 56. 合并区间
二、738. 单调递增的数字
三、968.监控二叉树
总结

前言

今天是算法营的第31天，希望自己能够坚持下来！
今日任务：
● 56. 合并区间
● 738.单调递增的数字
● 968.监控二叉树

一、 56. 合并区间

题目链接
文章讲解
视频讲解

思路：
1.先对区间以左边界进行排序
2.遍历区间，重叠的就对区间进行合并，更新右边界；不重叠的直接放入结果集
这里有个技巧，把第一个区间直接放入结果集，然后遍历的时候直接在结果集中进行合并区间

class Solution {
public:// static bool cmp(const vector<int>& a, const vector<int>& b) {//     return a[0] < b[0];// }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.push_back(intervals[0]);for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] <= result.back()[1]) { //重叠//合并区间，就是更新结果集里面的右边界，左边界已经按大小排序了，只有右边界需要判断取最大值result.back()[1] = max(intervals[i][1], result.back()[1]);} else {result.push_back({intervals[i][0], intervals[i][1]}); //不重叠}}return result;}
};

二、738. 单调递增的数字

题目链接
文章讲解
视频讲解

思路：

将数字转成字符串来处理
后序遍历，如果左边数字比当前数字大，记录当前数字位置flag，并且左边数字-1
记录的flag及以后的数字都变成9

代码如下：

class Solution {
public:int monotoneIncreasingDigits(int n) {string s = to_string(n); //转成字符串来处理int flag = s.size(); //记录需要变成9的数字位置for (int i = s.size() - 1; i > 0; i--) { //后序遍历，一直到第二个数字if (s[i - 1] > s[i]) { //左边数字比右边大flag = i;s[i - 1]--; //左边的数字-1，后面的数字全部变成9}}//flag位置及后面的数字全部变成9for (int i = flag; i < s.size(); i++) {s[i] = '9';}return stoi(s);}
};

三、968.监控二叉树

题目链接
文章讲解
视频讲解

思路：
整体思路是让叶子节点的父节点放监控，可以覆盖到叶子节点和父节点的父节点两层。

定义二叉树节点的三种状态：
0.无覆盖
1.有监控
2.有覆盖

思考空节点是什么状态：
空节点需要返回2有覆盖，因为空节点如果返回0和1都会影响“让叶子节点的父节点放监控”这个最初的设定。

思考遍历顺序：
需要左右节点反馈结果给中间节点，使用后序遍历。

递归三部曲：
1.递归的参数和返回值：参数是节点，返回值是自定义的三种节点状态（0,1,2）
2.终止条件：遇到空节点终止。
3.单层递归逻辑：
有三种情况：
情况一：左右节点都有覆盖，那么当前节点无覆盖，需要当前节点的父节点放监控，返回0
情况二：左右任一节点无覆盖，那么当前节点都需要放监控，返回1（result++）
情况三：左右任一节点有监控，那么当前节点就是有覆盖，返回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) {}* };*/
class Solution {
public:int result;//定义三种状态，0：无覆盖，1：有摄像头 2：有覆盖//叶子节点往上遍历，使用后序遍历（左右中）//叶子节点的父节点放摄像头int traversal(TreeNode* root) {//空节点返回2有覆盖if (root == nullptr) return 2;int left = traversal(root->left);int right = traversal(root->right);//1.左右节点都有覆盖，当前节点无覆盖，返回0（父节点安装摄像头）if (left == 2 && right == 2) return 0;//2.左右节点任意一个无覆盖，当前节点安装摄像头，返回1if (left == 0 || right == 0) {result++;return 1;}//3.左右节点任意一个有摄像头，当前节点有覆盖，返回2if (left == 1 || right == 1) return 2;return -1;}int minCameraCover(TreeNode* root) {result = 0;//4.根节点返回0，本来需要在其父节点安装摄像头来覆盖的，需要加多一个摄像头在根节点if (traversal(root) == 0) result++;return result;}
};