Day37｜贪心算法part06：738.单调递增的数字、968. 监控二叉树、贪心总结

本文主要是介绍Day37｜贪心算法part06：738.单调递增的数字、968. 监控二叉树、贪心总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

738. 单调递增的数字

总体思想就是从后往前遍历，比较第i位和第i+1位的大小，不符合顺序char[i]减1，i+1位填9，找到需要填9的最先位置，然后填9。

class Solution {public int monotoneIncreasingDigits(int n) {String s = String.valueOf(n);char[] chars = s.toCharArray();int start = s.length();for (int i = s.length() - 2; i >= 0; i--) {if (chars[i] > chars[i + 1]) {chars[i]--;start = i+1;}}for (int i = start; i < s.length(); i++) {chars[i] = '9';}return Integer.parseInt(String.valueOf(chars));}
}

数据转换：n → String → char[] → String→ n
Integer.parseInt：String->int
String.valueOf(n)：int → String

968. 监控二叉树

https://programmercarl.com/0968.%E7%9B%91%E6%8E%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E6%80%9D%E8%B7%AF

这题之前完全没做过，直接看题解了。

贪心：尽可能把摄像头放在非叶子结点，且从下往上看（指数级更省（
此时，大体思路就是从低到上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。

直接看代码，这里构造了虚拟根节点来将处理root的逻辑一般化：

class Solution {private int res = 0;private int traversal(TreeNode node){//0表示没被覆盖；//1表示装了摄像头；//2表示状态是被覆盖到。if(node == null){return 2;//2表示状态是被覆盖到。}int left = traversal(node.left);int right = traversal(node.right);//左右都被覆盖，在本结点肯定没被覆盖（按我们的贪心思想）if(left == 2 && right == 2){return 0;}//左右都没被覆盖，装摄像头if(left == 0 || right == 0){res++;//装摄像头return 1;}//左右有一个装了摄像头，本节点被照到
//            else if(left == 1 || right == 1){
//                return 2;
//            }else {return 2;}}public int minCameraCover(TreeNode root) {//考虑根节点是否被覆盖TreeNode dummyRoot = new TreeNode();dummyRoot.left = root;traversal(dummyRoot);return res;}}

贪心总结

https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E7%AF%87.html#%E8%B4%AA%E5%BF%83%E6%AF%8F%E5%91%A8%E6%80%BB%E7%BB%93

最近发现总结还有每道题的总结，之后大批量刷的时候根据总结去刷题。
在这里插入图片描述