济宁网站建设 果壳科技,cmseasy做网站简单吗,工业和信息化部直属大学,邯郸网站制作建设738.单调递增的数字 题目链接#xff1a;单调递增的数字 题目描述#xff1a;当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时#xff0c;我们称这个整数是单调递增的。 给定一个整数 n #xff0c;返回 小于或等于 n 的最大数字#xff0c;且数字呈 单调递增 。 解… 738.单调递增的数字 题目链接单调递增的数字 题目描述当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时我们称这个整数是单调递增的。 给定一个整数 n 返回 小于或等于 n 的最大数字且数字呈 单调递增 。 解题思想
题目要求小于等于N的最大单调递增的整数那么拿一个两位的数字来举例。
例如98一旦出现strNum[i - 1] strNum[i]的情况非单调递增首先想让strNum[i - 1]–然后strNum[i]给为9这样这个整数就是89即小于98的最大的单调递增整数。
从后向前遍历如果前一位大于后一位就将前一位减一后一位变为“9” 注意这里使用flag来标记赋值9从哪里开始flag后面的要全标为‘9’
class Solution {
public:int monotoneIncreasingDigits(int n) {string s to_string(n);int flag s.size();for (int i s.size() - 2; i 0; i--) {if (s[i] s[i 1]) {s[i] - 1;flag i 1;}}for (int i flag; i s.size(); i){s[i] 9;}int result 0;for (int i 0; i s.size(); i) {result result * 10 (s[i] - 0);}return result;}
};时间复杂度O(n)n 为数字长度空间复杂度O(n)需要一个字符串转化为字符串操作更方便 968.监控二叉树 题目链接监控二叉树 题目描述给定一个二叉树我们在树的节点上安装摄像头。 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。 计算监控树的所有节点所需的最小摄像头数量。 解题思想
从题目中示例其实可以得到启发我们发现题目示例中的摄像头都没有放在叶子节点上
所以我们要从下往上看局部最优让叶子节点的父节点安摄像头所用摄像头最少整体最优全部摄像头数量所用最少
此时这道题目还有两个难点
二叉树的遍历如何隔两个节点放一个摄像头
**确定遍历顺序**应采用后序遍历从下到上推倒。
如何隔两个节点放一个摄像头
此时需要状态转移的公式大家不要和动态的状态转移公式混到一起本题状态转移没有择优的过程就是单纯的状态转移看看这个状态应该如何转移先来看看每个节点可能有几种状态
0该节点无覆盖1本节点有摄像头2本节点有覆盖
主要有如下四类情况
情况1左右节点都有覆盖
左孩子有覆盖右孩子有覆盖那么此时中间节点应该就是无覆盖的状态了。
情况2左右节点至少有一个无覆盖的情况
如果是以下情况则中间节点父节点应该放摄像头
情况3左右节点至少有一个有摄像头
如果是以下情况其实就是 左右孩子节点有一个有摄像头了那么其父节点就应该是2覆盖的状态
情况4头结点没有覆盖
以上都处理完了递归结束之后可能头结点 还有一个无覆盖的情况
class Solution {
public:int minCameraCover(TreeNode* root) {if (traversal(root) 0) {result;}return result;}private:int result 0;int traversal(TreeNode* node) {if (node NULL)return 2;int left traversal(node-left);int right traversal(node-right);if (left 2 right 2)return 0;if (left 0 || right 0) {result;return 1;}if (left 1 || right 1)return 2;return -1;}
};时间复杂度: O(n)需要遍历二叉树上的每个节点空间复杂度: O(n)
