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()][]);}
}
)
