第八章 贪心算法 part06● 738.单调递增的数字
● 968.监控二叉树
● 总结 详细布置 738.单调递增的数字
https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html 968.监控二叉树 （可以跳过）本题是贪心和二叉树的一个结合，比较难，一刷大家就跳过吧。
https://programmercarl.com/0968.%E7%9B%91%E6%8E%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html 总结 可以看看贪心算法的总结，贪心本来就没啥规律，能写出个总结篇真的不容易了。
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
day36
单调递增的数字
class Solution {public int monotoneIncreasingDigits(int n) {//从后往前比较,前一位大则变小,并记录变成9的位置String s = String.valueOf(n);char ch[] = s.toCharArray();int flag = ch.length;for(int i = ch.length - 1; i > 0; i--){if(ch[i] < ch[i - 1]){ch[i - 1]--;//为什么?哦,52变成49,而不是22flag = i;//从flag开始后面都变成9}}for(int i = flag; i < ch.length; i++){//ch[i] = 9;//char类型,不正确ch[i] = '9';}return Integer.parseInt(String.valueOf(ch));}}
监控二叉树
class Solution {int result = 0;public int minCameraCover(TreeNode root) {//大体思路就是从低到上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。if(traversal(root) == 0 ){//处理根节点无覆盖的情况result++;}return result;}private int traversal(TreeNode root){//三种状态,1有摄像头,2有覆盖,0无覆盖if( root == null) return 2;//后序遍历int left = traversal(root.left);int right = traversal(root.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;//走不到这一步}}
贪心算法总结:
感谢大佬分享:
代码随想录-算法训练营day36【贪心算法06：单调递增的数字、监控二叉树、总结】-CSDN博客
