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;
}
};