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

本文主要是介绍代码随想录算法训练营第37天| Leetcode 738.单调递增的数字、968.监控二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

Leetcode 738.单调递增的数字
Leetcode 968.监控二叉树

Leetcode 738.单调递增的数字

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

给定一个整数 n ，返回小于或等于n的最大数字，且数字呈单调递增。
思路： 本题数据范围太大了，暴力解法肯定会超时，因此需要借助贪心思想优化。

如果是0~9的话返回其本身，也就是不需要任何操作；
如果是10~99，我们可以判断十位数字与个位数字的大小，比如73，我们需要做的操作就是将7--，然后3变成9，结果为69；
对于三位数及以上数字，可以从后两位开始判断，将其变为单调递增数字（局部最优），再逐渐判断更高一位的数字，最终数字整体变成单调递增数字（全局最优）。

基于以上思路，我们可以发现从后向前遍历数字更适合。这里还有一个小技巧：可以将数字转换成字符串，这样可以轻松获得每一位上的数字。 尽管这样增加了空间复杂度，但是代码更好写了。

代码如下：

class Solution {
public:int monotoneIncreasingDigits(int n) {string s = to_string(n);//字符串更方便操作每一位上的数字//用flag标记从哪个位置之后全赋值为9int flag = s.size();for (int i = s.size() - 1; i > 0; i--) {if (s[i - 1] > s[i]) {flag = i;s[i - 1]--;}}for (int i = flag; i < s.size(); i++) {s[i] = '9';}return stoi(s);}
};

时间复杂度： $O (n)$
空间复杂度： $O (n)$

Leetcode 968.监控二叉树

题目链接：Leetcode 968.监控二叉树
题目描述： 给定一个二叉树，我们在树的节点上安装摄像头。

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

计算监控树的所有节点所需的最小摄像头数量。

思路： 本题可以利用贪心思想，由于二叉树自上向下的节点个数是以指数级别增长，也就是说我们需要尽可能的让摄像头向上放而不聚集在叶子节点，这样可以节省大量摄像头数量，对应的我们需要利用二叉树的后序遍历，只有这样才是从下向上的判断是否需要添加摄像头。

代码如下：

class Solution {
public:int result; //统计摄像头数量// 0代表无覆盖，1代表摄像头，2代表有覆盖int traversal(TreeNode* cur) {//空节点，假设为有覆盖if (cur == nullptr)return 2;int left = traversal(cur->left);int right = traversal(cur->right);//(1)左右孩子都为2,则父节点为0if (left == 2 && right == 2)return 0;//(2)左右孩子至少有一个为0，则父节点为1// left == 0 && right == 0 左右节点无覆盖// left == 1 && right == 0 左节点有摄像头，右节点无覆盖// left == 0 && right == 1 左节点有无覆盖，右节点摄像头// left == 0 && right == 2 左节点无覆盖，右节点覆盖// left == 2 && right == 0 左节点覆盖，右节点无覆盖if (left == 0 || right == 0) {result++;return 1;}//(3)左右孩子至少有一个为1，则父节点为2if (left == 1 || right == 1)return 2;//所有情况已经讨论结束，但是没有这段代码leetcode编译不过return -1;}int minCameraCover(TreeNode* root) {result = 0;//不要漏掉这里：(4)回溯到最后可能根节点未被覆盖if (traversal(root) == 0)result++;return result;}
};

时间复杂度: $O (n)$
空间复杂度: $O (n)$