Day 28
題目描述
思路
初次思路：借鑒一下昨天題解的思路，將插入的區間與區間數組作比較，插入到升序的數組中，其他的和（合并區間）做法一樣。
注意需要特殊處理一下情況，插入區間比數組中最后一個區間的起始點大，這種情況，在循環中不會計算到插入區間，單獨處理一下。
class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {List<int[]> merged = new ArrayList<int[]>();if(intervals.length==0){//區間數組為空merged.add(new int[]{newInterval[0],newInterval[1]});return merged.toArray(new int[merged.size()][]); }int start=0,end=0;for (int i = 0; i < intervals.length;i++) {if(newInterval[0]<intervals[i][0]) {//將插入區間到數組中start = newInterval[0];end = newInterval[1];newInterval[0] = intervals[i][0];newInterval[1] = intervals[i][1];i--;}else{start = intervals[i][0];end = intervals[i][1];}if(merged.size()==0||merged.get(merged.size()-1)[1]<start) {merged.add(new int[]{start, end});}else{merged.get((merged.size()-1))[1] = Math.max(merged.get(merged.size()-1)[1], end);}}if(newInterval[0]>=intervals[intervals.length-1][0]){//特殊處理一下if(merged.size()==0||merged.get(merged.size()-1)[1]<newInterval[0]) {merged.add(new int[]{newInterval[0], newInterval[1]});}else{merged.get((merged.size()-1))[1] = Math.max(merged.get(merged.size()-1)[1], newInterval[1]);}}return merged.toArray(new int[merged.size()][]); }
}
問題：時間復雜度比較高，雖然通過了
做法：注意題目條件，給定的區間數組中的區間是不重疊的，那么我們需要插入一個新的區間，只需要找到這個與這個插入區間有重疊的區間，合并成一個大區間即可。
class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {List<int[]> res = new ArrayList<int[]>();if(intervals.length==0){//數組為空特殊處理res.add(new int[]{newInterval[0],newInterval[1]});return res.toArray(new int[res.size()][]);}int x=0;int start =newInterval[0],end=newInterval[1];//初始化for (int i = 0; i < intervals.length; i++) {if(intervals[i][1] <newInterval[0]) {//說明這個區間和新插入區間沒有交集res.add(new int[]{intervals[i][0],intervals[i][1]});}else if(intervals[i][0] > newInterval[1]) {if(x==0){//由于數組是按照起始點的升序排列。證明插入的區間到這里已經找到最大的合并區間res.add(new int[]{start,end});x=1;}//說明這個區間和新插入區間沒有交集res.add(new int[]{intervals[i][0],intervals[i][1]});}else{//擴大合并區間start=Math.min(start,intervals[i][0]);end=Math.max(end,intervals[i][1]);}}if(x==0){//排除特殊情況，即為數組中所有區間在插入這個區間后合并為一個大區間res.add(new int[]{start,end});}return res.toArray(new int[res.size()][]);}
}
題目描述
思路
首先我們來中翻中一下：這題所謂的最少數量的箭，可以理解為多個區間中的重疊的區間，所以這道題的目的是為了找到這個區間數組有幾個重疊區間。
做法：
- 將所有氣球按照起始點升序進行排序
- 創建start和end，用來記錄當前重合區間的范圍（初始設置為第一個氣球的范圍），初始設置箭數sum為1。
- 從前向后遍歷，由于此時氣球是有序的，比較當前氣球和重合范圍（start，end）是否重合，也就是比較當前氣球的起始點是否小于等于end（不比較start的原因在于是升序的，下一個氣球的起始點一定比start大）
- 如果小于等于end，說明氣球在重合區間，需要更新重合區間（這里建議畫圖理解），更新看代碼。
- 如果大于end，說明這個氣球和之前的所有氣球不能一箭射穿，就將箭數加1
注意：箭初始設置為1，目的就是將與第一個氣球有重合區間的所有氣球都射穿，如果一個氣球不在重合區間，就需要多一把箭。
class Solution {public int findMinArrowShots(int[][] points) {if(points.length==0){//為空特殊處理return 0;}int start=0,end=0,sum=1;Arrays.sort(points, new Comparator<int[]>() {//按照起始點進行升序排序public int compare(int[] interval1, int[] interval2) {return Integer.compare(interval1[0], interval2[0]);}});//排序start=points[0][0];end=points[0][1];for(int i=1;i<points.length;i++){if(points[i][0]<=end){//如果該區間的起始點比目前記錄的區間結束點還小，說明有重合start=Math.max(start,points[i][0]);//修改區間的起始點end=Math.min(end,points[i][1]);//修改區間的結束點//這里就是收縮到目前的最小重合區間}else{//說明這個氣球不在之前的重合區間，一箭射不爆sum++;//計數器加1 start=points[i][0];end=points[i][1];//將這個氣球的范圍作為新的區間}}return sum;}
}
