452. 用最少數量的箭引爆氣球
題目(求無重復區間)
有一些球形氣球貼在一堵用 XY 平面表示的墻面上。墻面上的氣球記錄在整數數組 points ，其中points[i] = [xstart, xend] 表示水平直徑在 xstart 和 xend之間的氣球。你不知道氣球的確切 y 坐標。
一支弓箭可以沿著 x 軸從不同點 完全垂直 地射出。在坐標 x 處射出一支箭，若有一個氣球的直徑的開始和結束坐標為 x``start，x``end， 且滿足 xstart ≤ x ≤ x``end，則該氣球會被 引爆 。可以射出的弓箭的數量 沒有限制 。 弓箭一旦被射出之后，可以無限地前進。
給你一個數組 points ，返回引爆所有氣球所必須射出的 最小 弓箭數 。
示例 1：
輸入：points = [[10,16],[2,8],[1,6],[7,12]]
輸出：2
解釋：氣球可以用2支箭來爆破:
-在x = 6處射出箭，擊破氣球[2,8]和[1,6]。
-在x = 11處發射箭，擊破氣球[10,16]和[7,12]。
示例 2：
輸入：points = [[1,2],[3,4],[5,6],[7,8]]
輸出：4
解釋：每個氣球需要射出一支箭，總共需要4支箭。
示例 3：
輸入：points = [[1,2],[2,3],[3,4],[4,5]]
輸出：2
解釋：氣球可以用2支箭來爆破:
- 在x = 2處發射箭，擊破氣球[1,2]和[2,3]。
- 在x = 4處射出箭，擊破氣球[3,4]和[4,5]。
答案
class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));//不會溢出int res = 1;for(int i=1;i<points.length;i++){if(points[i][0]>points[i-1][1]){res++;}else{points[i][1] = Math.min(points[i-1][1],points[i][1]);}}return res;}
}
435. 無重疊區間
題目
給定一個區間的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除區間的最小數量，使剩余區間互不重疊 。
示例 1:
輸入: intervals = [[1,2],[2,3],[3,4],[1,3]]
輸出: 1
解釋: 移除 [1,3] 后，剩下的區間沒有重疊。
示例 2:
輸入: intervals = [ [1,2], [1,2], [1,2] ]
輸出: 2
解釋: 你需要移除兩個 [1,2] 來使剩下的區間沒有重疊。
示例 3:
輸入: intervals = [ [1,2], [2,3] ]
輸出: 0
解釋: 你不需要移除任何區間，因為它們已經是無重疊的了。
答案
class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));int res = 1;for(int i=1;i<intervals.length;i++){if(intervals[i][0]>=intervals[i-1][1]){res++;}else{intervals[i][1] = Math.min(intervals[i-1][1],intervals[i][1]);}}return intervals.length - res;}
}
763. 劃分字母區間
題目
給你一個字符串 s 。我們要把這個字符串劃分為盡可能多的片段，同一字母最多出現在一個片段中。
注意，劃分結果需要滿足：將所有劃分結果按順序連接，得到的字符串仍然是 s 。
返回一個表示每個字符串片段的長度的列表。
示例 1：
輸入：s = "ababcbacadefegdehijhklij"
輸出：[9,7,8]
解釋：
劃分結果為 "ababcbaca"、"defegde"、"hijhklij" 。
每個字母最多出現在一個片段中。
像 "ababcbacadefegde", "hijhklij" 這樣的劃分是錯誤的，因為劃分的片段數較少。
示例 2：
輸入：s = "eccbbbbdec"
輸出：[10]
答案
class Solution {public List<Integer> partitionLabels(String s) {int[] arr = new int[26];for(int i=0;i<s.length();i++){arr[s.charAt(i)-'a'] = i;}int pre = -1;int post = 0;List<Integer> list = new ArrayList(); for(int i=0;i<s.length();i++){post = Math.max(post,arr[s.charAt(i)-'a']);if(i==post){list.add(post-pre);pre = post;}}return list;}
}
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] 可被視為重疊區間。
答案
class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));List<int[]> list = new ArrayList();int start = intervals[0][0];int end = intervals[0][1];for(int i=1;i<intervals.length;i++){if(intervals[i][0]>end){list.add(new int[]{start,end});start = intervals[i][0];end = intervals[i][1];}else{ end = Math.max(end,intervals[i][1]);}}list.add(new int[]{start,end});return list.toArray(new int[list.size()][]);}
}
738. 單調遞增的數字
題目
當且僅當每個相鄰位數上的數字 x 和 y 滿足 x <= y 時，我們稱這個整數是單調遞增的。
給定一個整數 n ，返回 小于或等于 n 的最大數字，且數字呈 單調遞增 。
示例 1:
輸入: n = 10
輸出: 9
示例 2:
輸入: n = 1234
輸出: 1234
示例 3:
輸入: n = 332
輸出: 299
答案
class Solution {public int monotoneIncreasingDigits(int n) {String[] strs = (n+"").split("");int start = strs.length;for(int i=strs.length-1;i>0;i--){if(Integer.parseInt(strs[i-1])>Integer.parseInt(strs[i])){strs[i-1] = (Integer.parseInt(strs[i-1])-1)+"";start = i;}}for(int i=start;i<strs.length;i++){strs[i] = "9";}return Integer.parseInt(String.join("",strs));}
}
968. 監控二叉樹
題目
給定一個二叉樹，我們在樹的節點上安裝攝像頭。
節點上的每個攝影頭都可以監視其父對象、自身及其直接子對象。
計算監控樹的所有節點所需的最小攝像頭數量。
示例 1：
輸入：[0,0,null,0,0]
輸出：1
解釋：如圖所示，一臺攝像頭足以監控所有節點。
示例 2：
輸入：[0,0,null,0,null,0,null,null,0]
輸出：2
解釋：需要至少兩個攝像頭來監視樹的所有節點。 上圖顯示了攝像頭放置的有效位置之一。
答案
class Solution {int res;public int minCameraCover(TreeNode root) {if(deal(root)==0){res++;}return res;}int deal(TreeNode root){//0 沒有被監控 1 放監控 2 孩子監控 后序遍歷if(root==null){return 2;}int left = deal(root.left);int right = deal(root.right);if(left==2 && right==2){return 0;}else if(left==0 || right==0){res++;return 1;}else{return 2;}}
}
)
