56. 合并区间
思路：这个题跟气球重叠区间的题目类似，只需要先按左边界进行排序，判断是否重叠，如果重叠，就选择最小的左边界和最大的右边界构成新的区间。
代码如下：
class Solution {public int[][] merge(int[][] intervals) {LinkedList<int[]> list=new LinkedList<>();Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));list.add(intervals[0]);for(int i=1;i<intervals.length;i++){if(intervals[i][0]<=list.getLast()[1]){int start=list.getLast()[0];int end=Math.max(intervals[i][1], list.getLast()[1]);list.removeLast();list.add(new int[]{start,end});}else{list.add(intervals[i]);}}return list.toArray(new int[list.size()][]);}
}
738.单调递增的数字
思路：局部解题方法：比如98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]–，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。全局思路：从后往前遍历。
代码如下：
class Solution {public int monotoneIncreasingDigits(int n) {String s=String.valueOf(n);char[] chars=s.toCharArray();int start=chars.length;for(int i=chars.length-1;i>0;i--){if(chars[i-1]>chars[i]){chars[i-1]--;start=i;}}for(int i=start;i<chars.length;i++) {chars[i]='9';}return Integer.parseInt(String.valueOf(chars));}
}
注意：考虑到有100，1000这样的数存在，所以需要记录修改的点，并将后面的所有值填充为9.
968.监控二叉树
思路：如果是从根节点开始遍历可能会重复计算，所以最好使用后序遍历。考虑到叶子节点都没有监控点，监控点会分布在叶子节点的上一层；同时可以监控到监控点的上一层节点。也就是说，把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。
此时，大体思路就是从低到上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。使用全局变量result来记录摄像头个数。
此时这道题目还有一个难点：如何隔两个节点放一个摄像头
解决这个问题需要状态转移的公式，每个节点可能有三种状态，分别用数字表示：
- 0:该节点无覆盖
- 1:本节点有摄像头
- 2:本节点有覆盖
递归三部曲：
-
传入参数；根节点，返回值为int类型（节点的状态）
-
终止条件：空节点的状态应该是有覆盖，这样就可以在叶子节点的父节点放摄像头了。所以递归的终止条件应该是遇到了空节点，此时应该返回2（有覆盖）。
-
递归函数单层逻辑：主要有如下四类情况：
情况1：左右节点都有覆盖
左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。
情况2：左右节点至少有一个无覆盖的情况，则中间节点（父节点）应该放摄像头。
情况3：左右节点至少有一个有摄像头，那么其父节点就应该是2（覆盖的状态）
情况4：头结点没有覆盖，所以递归结束之后，还要判断根节点，如果没有覆盖，result++。
代码如下：
class Solution {int result=0;public int minCameraCover(TreeNode root) {if(treeStatus(root)==0) result++;return result;}public int treeStatus(TreeNode root){if(root==null) return 2;int left=treeStatus(root.left);int right=treeStatus(root.right);if(left==0 || right==0){result++;return 1;}else if(left==1 || right==1){return 2;}else {return 0;}}
}
