合并区间
题目：以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
解法：重叠区域类似。
public int[][] merge(int[][] intervals) {if (intervals == null || intervals.length == 0) {return new int[0][];}Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));List<int[]> result = new LinkedList<>();
//这在更改原数组，易造成元素丢失。int[] currentInterval = intervals[0];for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] > currentInterval[1]) {result.add(currentInterval);currentInterval = intervals[i];} else {currentInterval[1] = Math.max(currentInterval[1], intervals[i][1]);}}result.add(currentInterval);return result.toArray(new int[result.size()][]);}
单调递增的数字
题目：当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例 1:
输入: n = 332
输出: 299
解法：：首先想让strNum[i - 1]减一，strNum[i]赋值9。从后往前遍历。
public int monotoneIncreasingDigits(int n) {String s = String.valueOf(n);char[] nums = s.toCharArray();int flag = s.length();//遍历的时候不符合的之后的数改为9.for (int i = s.length()-2; i >= 0 ; i--) {if (nums[i] > nums[i+1]){nums[i]--;flag = i +1;}}for (int i = flag; i < s.length(); i++) {nums[i] = '9';}return Integer.parseInt(String.valueOf(nums));
}监控二叉树
题目：给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
贪心：找到链接最多的节点。整体采取后序遍历。让叶子节点的父节点有摄像头。
每个节点的状态：1.有摄像头。2.有覆盖。0.覆盖。空节点为有覆盖。
整体情况：一个摄像头最大可以覆盖上层与下层。
- 左右都有覆盖。（空节点为状态2)
- 左右至少有一个状态0
- 左右至少有一个状态2。
- 根节点需要有状态1。
图解
a/ x/ \ Z Y
class Solution {int result = 0;public int minCameraCover(TreeNode root) {if (traval(root) == 0){result++;}return result;}public int traval(TreeNode node){if (node == null){return 2;//返回状态}int left = traval(node.left);int right = traval(node.right);if(left ==2 &&right == 2 ){return 0;}if (left == 0 ||right ==0){// 左右节点都是无覆盖状态,那 根节点此时应该放一个摄像头// (0,0) (0,1) (0,2) (1,0) (2,0)// 状态值为 1 摄像头数 ++;result++;return 1;}if (left == 1 ||right ==1){// 左右节点的 状态为 (1,1) (1,2) (2,1) 也就是左右节点至少存在 1个摄像头，// 那么本节点就是处于被覆盖状态return 2;}return -1;}
}