Day 27
題目描述
思路
做法：
- 特殊處理空數組和數組只有一個元素的情況
- 設置beg，end標記范圍的起始和結束，x用來比較元素是否有序（初始end和beg都指向nums[0[,x為nums[0]+1）
- 遍歷數組
- 如果當前元素等于x，說明他和上一個元素是有序的，x++,并且將end指向它
- 如果當前元素不是x，說明該元素與前一個元素不有序，處理
- 如果此時end==beg，說明只有一個元素有序，直接加入結果集合
- 如果beg！=end說明，存在起始和結束點，組合成規定形式，加入結果集合
- 清空字符串修改beg，end都指向當前元素，x=當前元素值加1
- 遍歷到最后一個元素需要特殊處理（原因在于最后一個元素如果與前一個有序，會直接結束循環，不有序也只是指向了它并沒有加入結果集）
class Solution {public List<String> summaryRanges(int[] nums) {ArrayList<String> list = new ArrayList<>();String s="";if(nums.length == 0) return list;if(nums.length == 1) list.add(String.valueOf(nums[0]));int beg=nums[0],end=nums[0],x=beg+1;StringBuilder sb = new StringBuilder(s);for (int i = 1; i < nums.length; i++) {if(x==nums[i]){x++;end=nums[i];}else {if(end==beg){sb.append(end);list.add(sb.toString());}else{sb.append(beg+"->"+end);list.add(sb.toString());}sb.delete(0,sb.length());beg=end=nums[i];x=beg+1;}if(i==nums.length-1){if(beg==nums[i]){sb.append(end);list.add(sb.toString());}else{list.add(beg+"->"+nums[i]);}}}return list;}
}
題目描述
思路
初次做法：對于兩個范圍是否能夠合并，有以下幾種情況用范圍（a，b）和（a1,b1）表示
- a a1 b1 b
- a1 a b b1
- a a1 b b1
- a1 a b1 b
- a1 b1 a b (b1==a)
- a b a1 b (b==a1)
我的做法是從前向后遍歷，處理每個元素與其之后的元素進行合并，將合并結果存放在后面的元素中，如果哪次循環沒有完成合并，說明取得的就是最大合并區間 ，取出來存放。
class Solution {public int[][] merge(int[][] intervals) {int[]beg=new int[intervals.length];int[]end=new int[intervals.length];int sum=0;int x=0;for (int i = 0; i < intervals.length; i++) {beg[sum] = intervals[i][0];end[sum] = intervals[i][1];x=0;for (int j = i + 1; j < intervals.length; j++) {if( (beg[sum]<=intervals[j][0]&&end[sum]>=intervals[j][0]&&end[sum]<=intervals[j][1])||(beg[sum]>=intervals[j][0]&&end[sum]<=intervals[j][1])||(beg[sum]<=intervals[j][0]&&end[sum]>=intervals[j][1]&&beg[sum]>=intervals[j][0])||(beg[sum]<=intervals[j][0]&&end[sum]>=intervals[j][1])||(beg[sum]>=intervals[j][0]&&end[sum]>=intervals[j][1]&&beg[sum]<=intervals[j][1])) {x=1;intervals[j][0]=Math.min(beg[sum],intervals[j][0]);intervals[j][1]=Math.max(end[sum],intervals[j][1]);}}if(x==0){sum++;}}int[][] result=new int[sum][2];for (int i = 0; i < sum; i++) {result[i][0] = beg[i];result[i][1] = end[i];}return result;}
}
題解做法：按照區間的左端點排序，那么在排完序的列表中，可以合并的區間一定是連續的。如果當前區間的左端點在數組 merged 中最后一個區間的右端點之后，那么它們不會重合，我們可以直接將這個區間加入數組 merged 的末尾；否則，它們重合，我們需要用當前區間的右端點更新數組 merged 中最后一個區間的右端點，將其置為二者的較大值。
class Solution {public int[][] merge(int[][] intervals) {if (intervals.length == 0) {return new int[0][2];}Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}});List<int[]> merged = new ArrayList<int[]>();for (int i = 0; i < intervals.length; ++i) {int L = intervals[i][0], R = intervals[i][1];if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {merged.add(new int[]{L, R});} else {merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);}}return merged.toArray(new int[merged.size()][]);}
}
)
