LeetCode T738 单调递增的数字
题目链接:738. 单调递增的数字 - 力扣（LeetCode）
题目思路:
我们以332举例,题目要我们获得的是小于等于332的最大递增数字,我们知道这个数字要递增只能取299了,332 -- 329 --299 我们从后向前遍历,只要前一位大于后一位,我们就减少前一位的数值,由于需要最大,我们后一位取9即可,以此类推就得到了299.
为什么不从前向后遍历呢?
我们不妨试试看332 -> 329 因为前两个是符合的33不变后面的32变成了29,明显不是我们需要的答案,这个只能满足最后两个数一定满足题意,而可能让前面的不满足题意
最后我们可以用一个start变量来标记需要标记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)); } }
LeetCode T968 监控二叉树
题目链接:968. 监控二叉树 - 力扣（LeetCode）
题目思路:
这题有点难度,我们就沿着卡哥的思路来理解,我们首先想,如何放置摄像头才是最少的呢,题目说了摄像头可以覆盖三层,要想他不浪费,那么根节点和叶子结点就是不能选择的,我们看示例也是这样写的,我们知道根节点处让摄像头物尽其用远不如叶子结点来节省的多,所以我们选择后序遍历,将上一个节点的覆盖情况通过返回值的形式返回上去
这题我们定义三种节点状态,0表示无覆盖,1表示有摄像头,2表示有覆盖
接下来我们讨论节点情况
注:空节点默认为已经覆盖的情况
假设空节点是没覆盖的情况,我们在叶子结点就得放摄像机来保证覆盖情况
1.左右孩子都有覆盖,那么为了更好的效果,此时父节点一定是没有覆盖的,父节点一定是要由他的父节点来覆盖的.
2.左右孩子有一个是没覆盖的,此时父节点一定要补一个摄像机,此时也要进行结果的累加
3.左右孩子有一个有摄像机,此时父节点一定是已经覆盖的
4.我们说头结点的覆盖要由他的父节点来完成,这里万一头结点就是根节点怎么办?这里我们做其他处理,也就是再加一个摄像头
题目代码:
class Solution { int result; public int minCameraCover(TreeNode root) { result = 0; if(travsal(root) == 0) { result++; } return result; } public int travsal(TreeNode root) { if(root == null) { return 2; } int left = travsal(root.left); int right = travsal(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; } }
