一、单调递增的数字
题目一：738. 单调递增的数字
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
从高位到低位遍历整数
n的每一位数字，当发现某一位数字大于其后一位数字时，将这一位数字减一，并将所有更低位的数字设置为 9，以确保结果是单调递增的。
/*
* @lc app=leetcode.cn id=738 lang=cpp
*
* [738] 单调递增的数字
*/
// @lc code=start
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string str = to_string(n);
int marker = str.size();
for (int i = str.size() - 1; i > 0; i--) {
if (str[i] < str[i - 1]) {
marker = i;
str[i - 1] = str[i - 1] - 1;
}
}
for (int i = marker; i < str.size(); i++) {
str[i] = '9';
}
return stoi(str);
}
};
// @lc code=end
二、监控二叉树
题目一：968. 监控二叉树
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
基本思路是从叶子节点开始向上，尽量在每个节点的父节点上安装摄像头，以覆盖尽可能多的节点。这样可以保证使用最少的摄像头覆盖所有节点。
可以定义三种状态：
- 0：这个节点尚未被覆盖。
- 1：这个节点有一个摄像头。
- 2：这个节点已被覆盖，但没有摄像头。
/*
* @lc app=leetcode.cn id=968 lang=cpp
*
* [968] 监控二叉树
*/
// @lc code=start
/**
* 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 minCameraCover(TreeNode* root) {
int cameras = 0;
int top = dfs(root, cameras);
return cameras + (top == 0 ? 1 : 0);
}
private:
int dfs(TreeNode* node, int& cameras) {
if (!node) return 2;
int left = dfs(node->left, cameras);
int right = dfs(node->right, cameras);
if (left == 0 || right == 0) {
cameras++;
return 1;
}
return (left == 1 || right == 1) ? 2 : 0;
}
};
// @lc code=end
