代码随想录算法训练营第三十七天 | 738.单调递增的数字、 968.监控二叉树

题目链接：738.单调递增的数字

文章讲解：代码随想录 738.单调递增的数字讲解

视频讲解：贪心算法，思路不难想，但代码不好写！LeetCode:738.单调自增的数字

思路和解法

题目：
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
想法：
关键思想在于从后向前遍历，遇到需要改的地方后面都需要改为9，所以就只记录最前面需要改的地方即可。

class Solution {
public://整体思路：从后向前遍历字符，如果i-1 < i那么i位置的要改为9，i-1位置的要减1//注意：一个位置改为了9，后面的位置都要改为9，所以只要记录第一个需要改为9的位置即可int monotoneIncreasingDigits(int n) {string s = to_string(n);//这里必须要初始化，防止在不需要任何改动时。不知道初始化值还是给改动了，所以初始化为一个不可能进行改动值int flag = s.size();for (int i = s.size() - 1; i > 0; i--) {if (s[i - 1] > s[i]) {//flag前一个位置-1，这个不能写在外面，否则不需要更改时也会把最后一位修改掉s[i - 1]--;flag = i;}}//进行修改，把flag以后的数字都改为9for (int i = flag; i < s.size(); i++) {s[i] = '9';}return stoi(s);}
};

题目链接：968.监控二叉树

文章讲解：代码随想录 968.监控二叉树讲解

视频讲解：贪心算法，二叉树与贪心的结合，有点难… LeetCode:968.监督二叉树

思路和解法

题目：
给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。
想法：
关键思想在于后序遍历二叉树，通过子节点的状态来判断当前节点的状态。还有比较难想的就是怎么划分状态，还有对每种状态的处理方式，直接看讲解还是比较符合思维习惯的，但是自己想不好想，还有最后对根节点无覆盖的处理非常容易忽视，遇到报错有可能会发现。

/*** 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://整体思路：为了尽可能少用摄像头，从下往上遍历二叉树，并把每个节点分为三种状态：0：无覆盖 1：有摄像头 2：有覆盖//对当前节点进行处理需要知道子节点的情况，因此递归函数有返回值，返回值就是当前节点的状态，而且还要后序遍历//当子节点中至少有一个无覆盖时，当前节点要设置摄像头；//剩下的情况不包含无覆盖，子节点至少有一个摄像头时，当前节点设置为有覆盖，子节点均为有覆盖时，当前节点设置为无覆盖//问题：空节点如何设置（返回什么）？空节点是不需要处理的节点，同时为了少用摄像头，希望空节点的父节点不要设置摄像头，所以不能将空节点设置为无覆盖//空节点的父节点其实是无覆盖，所以将空节点设置为有覆盖，这样其父节点的状态就会由零一个子节点决定//注意：遍历过程中遇到设置摄像头，记录摄像头结果数+1//记录摄像头数量int result = 0;//递归函数int traversal(TreeNode* node) {//终止条件：遇到了空节点if (node == nullptr) {return 2;}int left = traversal(node -> left);int right = traversal(node -> right);if (left == 0 || right == 0) {result++;return 1;} else if (left == 1 || right == 1) {return 2;} else {return 0;}}int minCameraCover(TreeNode* root) {int tmp = traversal(root);//注意：tmp接到的是root的状态，如果root状态是0，就还需要一个摄像头放在root上if (tmp == 0) result++;return result;}
};