Day 37 贪心算法
738. 单调递增的数字
两个可能经常要用到的函数
字符串转数字：to_string()
数字转字符串：stoi()文章来源：https://www.toymoban.com/news/detail-644373.html
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string num = to_string(n);
int len = num.size();
int flag = len;
for (int i = len - 1; i >= 1; i--)
{
if (num[i - 1] > num[i])
{
flag = i;
num[i - 1]--;
}
}
for (int i = flag; i < num.size(); i++)
{
num[i] = '9';
}
return stoi(num);
}
};
968. 监控二叉树
利用树后续遍历，同时加上状态转移的方法，非常值得反复学习文章来源地址https://www.toymoban.com/news/detail-644373.html
class Solution {
int rst;
// 0: 无覆盖, 1: 有摄像头, 2: 有覆盖
int tracking(TreeNode *root)
{
if (!root) return 2;
int leftStatus = tracking(root->left);
int rightStatus = tracking(root->right);
if (leftStatus == 2 && rightStatus == 2) return 0;
if (leftStatus == 0 || rightStatus == 0)
{
rst++;
return 1;
}
else return 2;
}
public:
int minCameraCover(TreeNode* root) {
rst = 0;
if (tracking(root) == 0) // 注意要接收这个返回值, 并作判断, 必要时rst++
{
rst++;
}
return rst;
}
};
到了这里，关于算法刷题Day 37 单调递增的数字+监听二叉树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
