56.合并區間

以數組 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].
示例 2：

輸入：intervals = [[1,4],[4,5]]
輸出：[[1,5]]
解釋：區間 [1,4] 和 [4,5] 可被視為重疊區間。

思路

首先還是按照左邊界排序。接下來合并區間。
直接在res里合并。

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, new Comparator<int[]>() {@Overridepublic int compare(int[] a, int[] b) {return a[0] - b[0];}});List<int[]> res = new ArrayList<>();res.add(intervals[0]);for (int i = 1; i < intervals.length; i++) {if (res.get(res.size() - 1)[1] >= intervals[i][0]) {res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], intervals[i][1]);} else {res.add(intervals[i]);}}return res.toArray(new int[res.size()][]);}
}

738.單調遞增的數字

當且僅當每個相鄰位數上的數字 x 和 y 滿足 x <= y 時，我們稱這個整數是單調遞增的。

給定一個整數 n ，返回 小于或等于 n 的最大數字，且數字呈 單調遞增 。

示例 1:

輸入: n = 10
輸出: 9
示例 2:

輸入: n = 1234
輸出: 1234
示例 3:

輸入: n = 332
輸出: 299

思路

一旦出現s[i-1]大于s[i]，非單調遞增，首先要讓s[i-1]–，比如332，3變成2。
從后向前遍歷，332->329->299，獲得了最前面的-1的位置，然后后面都是9即可。

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

968.監控二叉樹

給定一個二叉樹，我們在樹的節點上安裝攝像頭。

節點上的每個攝影頭都可以監視其父對象、自身及其直接子對象。

計算監控樹的所有節點所需的最小攝像頭數量。

思路

首先發現攝像頭都沒有放到葉節點上。
局部最優：葉節點的父節點安攝像頭
整體最優：全部攝像頭數量最少
所以從下向上，先給葉節點的父節點放攝像頭，然后隔兩個節點放一個攝像頭。
遍歷順序：左右中，從下向上，后序遍歷
定義每個節點的狀態：

• 節點無覆蓋：0
• 節點有攝像頭：1
• 節點有覆蓋：2
  空節點表示有覆蓋，這樣就可以不在葉節點放攝像頭了。

class Solution {int result;public int minCameraCover(TreeNode root) {result = 0;if (traversal(root) == 0) {// 頭節點無覆蓋，安裝攝像頭result++;}return result;}int traversal(TreeNode root) {// 空節點有覆蓋，返回2if (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;}
}