襄阳网站建设外包,自己做一个网站,外贸平台自建站,lol门户网站源码一、单调递增的数字
题目一#xff1a;738. 单调递增的数字
738. 单调递增的数字
当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时#xff0c;我们称这个整数是单调递增的。
给定一个整数 n #xff0c;返回 小于或等于 n 的最大数字#xff0c;且数字呈 单调递… 一、单调递增的数字
题目一738. 单调递增的数字
738. 单调递增的数字
当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时我们称这个整数是单调递增的。
给定一个整数 n 返回 小于或等于 n 的最大数字且数字呈 单调递增 。 从高位到低位遍历整数 n 的每一位数字当发现某一位数字大于其后一位数字时将这一位数字减一并将所有更低位的数字设置为 9以确保结果是单调递增的。 /** lc appleetcode.cn id738 langcpp** [738] 单调递增的数字*/// lc codestart
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 codeend
二、监控二叉树
题目一968. 监控二叉树
968. 监控二叉树
给定一个二叉树我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。 基本思路是从叶子节点开始向上尽量在每个节点的父节点上安装摄像头以覆盖尽可能多的节点。这样可以保证使用最少的摄像头覆盖所有节点。 可以定义三种状态 0这个节点尚未被覆盖。1这个节点有一个摄像头。2这个节点已被覆盖但没有摄像头。 /** lc appleetcode.cn id968 langcpp** [968] 监控二叉树*/// lc codestart
/*** 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 codeend
