Day36 单调递增的数字 + 监控二叉树

738 单调递增的数字

题目链接：https://leetcode.cn/problems/monotone-increasing-digits/description/

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

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

输入: n = 10
输出: 9

输入: n = 1234
输出: 1234

输入: n = 332
输出: 299

思路：
从右向左不断找不满足递增条件的数字，将不满足的数字-1，最后一个数字后面的数字都改为9。

例如332，分别变为322、222、299。

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strNum = to_string(n);
        int flag = strNum.size();
        for (int i = strNum.size() - 1; i > 0; i--) {
            if (strNum[i - 1] > strNum[i] ) {
                flag = i;
                strNum[i - 1]--;
            }
        }
        for (int i = flag; i < strNum.size(); i++) {
            strNum[i] = '9';
        }
        return stoi(strNum);
    }
};

968 监控二叉树

题目链接：https://leetcode.cn/problems/binary-tree-cameras/

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

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

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

思路：

对每个节点，标记3种状态。
0：不能被覆盖到
1：需放相机
2：可以被孩子覆盖/null

使用后序遍历获取左右孩子，left、right

• 叶子节点返回0 if(left == 2 && right == 2) return 0;
• 若孩子有未被覆盖的，需放相机 if(left == 0 || right == 0) return 1;
• 其余情况返回2

class Solution {
public:
    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;
    }

    int minCameraCover(TreeNode* root) {
        result = 0;
        if (traversal(root) == 0) { // root 无覆盖
            result++;
        }
        return result;
    }
};