LeetCode:738.单调递增的数字
1.思路
倒序遍历，将当前位置数字与之后数字进行比较，当大于后者，做--同时后者取9，当小于时继续遍历即可，最后将start + 1及之后位置的数值赋为9.
2.代码实现
1// 2class Solution { 3 public int monotoneIncreasingDigits(int n) { 4 String s = String.valueOf(n); 5 char[] ch = s.toCharArray(); 6 7 int start = ch.length; 8 for (int i = ch.length - 2; i >= 0; i--) { 9 if (ch[i] > ch[i + 1]) { 10 ch[i]--; 11 start = i + 1; 12 } 13 } 14 for (int i = start ; i < ch.length; i++) { 15 ch[i] = '9'; 16 } 17 return Integer.parseInt(String.valueOf(ch)); 18 } 19} 20 21 22// ChatGPT打辅助 23class Solution { 24 public int monotoneIncreasingDigits(int n) { 25 // 将整数n转换为字符串 26 String s = String.valueOf(n); 27 // 将字符串转换为字符数组 28 char[] chars = s.toCharArray(); 29 // 记录需要修改的起始位置，默认为字符串的长度 30 int start = s.length(); 31 // 从倒数第二位开始向前遍历字符数组 32 for (int i = s.length() - 2; i >= 0; i--) { 33 // 如果当前字符大于后一个字符，则将当前字符减1，并记录修改的起始位置 34 if (chars[i] > chars[i + 1]) { 35 chars[i]--; 36 start = i + 1; 37 } 38 } 39 // 将修改起始位置后的所有字符置为9 40 for (int i = start; i < s.length(); i++) { 41 chars[i] = '9'; 42 } 43 // 将字符数组转换为整数并返回 44 return Integer.parseInt(String.valueOf(chars)); 45 } 46} 47 48 49// 暴力实现：超时 50class Solution { 51 public int monotoneIncreasingDigits(int n) { 52 // 个位数 -> 十位数 -> ... 53 List<Integer> res = new ArrayList<>(); 54 for (int i = n; i >= 0; i--) { 55 if (isMonotoneIncreasing(i)) { 56 res.add(i); 57 break; 58 } 59 } 60 return res.get(res.size() - 1); 61 } 62 63 public boolean isMonotoneIncreasing(int number) { 64 int prevDigit = Integer.MAX_VALUE; 65 while (number > 0) { 66 int curDigit = number % 10; 67 if (curDigit > prevDigit) { 68 return false; 69 } 70 prevDigit = curDigit; 71 number /= 10; 72 } 73 return true; 74 } 75}
3.复杂度分析
时间复杂度：O(n + m).
空间复杂度：O(1).
4.方法及心得
数字转为字符串，再转为字符数组（String修饰的字符串不可变，不能直接修改）
Integer.parseInt(String.valueOf(ch)) 是将字符数组 ch 转换为整数的方法。
首先，String.valueOf(ch) 将字符数组 ch 转换为一个字符串。然后，Integer.parseInt() 方法将该字符串解析为一个整数。
具体来说，Integer.parseInt() 方法将字符串中的字符按照整数的规则进行解析。它会忽略字符串开头和末尾的空格，并且可以处理正负号。如果字符串无法解析为一个合法的整数，Integer.parseInt() 方法会抛出一个 NumberFormatException 异常。
LeetCode:968.监控二叉树
1.思路
很多情况导致难以下手，首先可以想遍历顺序，前？中？后？孩子节点大于根节点，选择后序可以尽可能少的放置一些摄像头。其次，放置摄像头的情况，①孩子节点的父节点放置摄像头，并作标记0，无覆盖；②左孩子或右孩子某一个无覆盖，摄像头+1；③其他情况表示有覆盖返回2；
2.代码实现
1class Solution { 2 int res = 0; 3 public int minCameraCover(TreeNode root) { 4 5 if (minCame(root) == 0) { 6 res++; 7 } 8 return res; 9 } 10 public int minCame(TreeNode root) { 11 if (root == null) { 12 return 2; 13 } 14 15 int left = minCame(root.left); 16 int right = minCame(root.right); 17 18 if (left == 2 && right == 2) { 19 return 0; 20 } else if (left == 0 || right == 0) { 21 res++; 22 return 1; 23 } else { 24 return 2; 25 } 26 } 27}
3.复杂度分析
时间复杂度：O(n).
空间复杂度：O(n).
