LeetCode:435. 无重叠区间
1.思路
无序的数组表，去重复区间，首先进行排序，依据区间一侧进行判重处理，以右边界为届.
计数分为正向计数和逆向计数，区别在于是否符合重复区间的位置不同.
2.代码实现
1// 正向计数逻辑 2class Solution { 3 public int eraseOverlapIntervals(int[][] intervals) { 4 Arrays.sort(intervals, (a, b) -> { 5 return Integer.compare(a[0], b[0]); 6 }); 7 int rem = 0; 8 int pre = intervals[0][1]; 9 for (int i = 1; i < intervals.length; i++) { 10 if (pre > intervals[i][0]) { 11 rem++; 12 pre = Math.min(pre, intervals[i][1]); 13 } else { 14 pre = intervals[i][1]; 15 } 16 } 17 return rem; 18 } 19} 20 21// 逆向计数逻辑 22class Solution { 23 public int eraseOverlapIntervals(int[][] intervals) { 24 Arrays.sort(intervals, (a, b) -> { 25 return Integer.compare(a[0], b[0]); 26 }); 27 int count = 1; 28 for (int i = 1; i < intervals.length; i++) { 29 if (intervals[i - 1][1] > intervals[i][0]) { 30 intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]); 31 } else { 32 count++; 33 } 34 } 35 return intervals.length - count; 36 } 37}
3.复杂度分析
时间复杂度：O(n + nlogn).
空间复杂度：O(n)
LeetCode:763.划分字母区间
1.思路
创建一个26大小的数组来存放26个字母出现在s中的最大索引，遍历即可，字符串转换为字符数组(这一步可以省略，字符串遍历也一样)。再次遍历字符串更新当前索引范围下的字母最远索引，当idx == edge[s.charAt(i) - 'a']时，添加到结果集中，继续下一段遍历.
2.代码实现
1// 字符数组实现，中间多一步转化 2class Solution { 3 public List<Integer> partitionLabels(String s) { 4 List<Integer> list = new ArrayList<>(); 5 int[] edge = new int[26]; 6 char[] charS = s.toCharArray(); 7 for (int i = 0; i < charS.length; i++) { 8 edge[charS[i] - 'a'] = i; 9 } 10 int idx = 0; 11 int right = 0; 12 for (int i = 0; i < charS.length; i++) { 13 idx = Math.max(idx, edge[charS[i] - 'a']); 14 if (i == idx) { 15 list.add(i - right + 1); 16 right = i + 1; 17 } 18 } 19 return list; 20 } 21} 22 23// 字符串实现 24class Solution { 25 public List<Integer> partitionLabels(String s) { 26 List<Integer> list = new ArrayList<>(); 27 int[] edge = new int[26]; 28 for (int i = 0; i < s.length(); i++) { 29 edge[s.charAt(i) - 'a'] = i; 30 } 31 int idx = 0; 32 int right = 0; 33 for (int i = 0; i < s.length(); i++) { 34 idx = Math.max(idx, edge[s.charAt(i) - 'a']); 35 if (i == idx) { 36 list.add(i - right + 1); 37 right = i + 1; 38 } 39 } 40 return list; 41 } 42}
时间复杂度：O(n).
空间复杂度：O(1).
LeetCode:56. 合并区间
56. 合并区间 - 力扣（LeetCode）
1.思路
抄完上面几个题目之后，这个思路挺清晰的：先排序，而后遍历合并重叠区间，非重叠区间直接加入结果集即可，注意最后一组元素是最后直接加入结果集！！！
学到了链表和数组的结合体的处理方式
2.代码实现
1// 第一种 2class Solution { 3 public int[][] merge(int[][] intervals) { 4 // 重叠的合并，不重叠的加入即可 5 // 排序 6 List<int[]> res = new ArrayList<>(); 7 8 Arrays.sort(intervals, (a, b) -> { 9 return Integer.compare(a[0], b[0]); 10 }); 11 int pre1 = intervals[0][0]; 12 int pre2 = intervals[0][1]; 13 for (int i = 1; i < intervals.length; i++) { 14 if (pre2 >= intervals[i][0]) { 15 pre2 = Math.max(pre2, intervals[i][1]); 16 } else { 17 res.add(new int[]{pre1, pre2}); 18 pre1 = intervals[i][0]; 19 pre2 = intervals[i][1]; 20 } 21 } 22 res.add(new int[]{pre1, pre2}); 23 return res.toArray(new int[res.size()][]); 24 } 25} 26 27// 第二种 28class Solution { 29 public int[][] merge(int[][] intervals) { 30 // 重叠的合并，不重叠的加入即可 31 // 排序 32 List<List<Integer>> res = new ArrayList<>(); 33 34 Arrays.sort(intervals, Comparator.comparingInt(a -> a[0])); 35 int pre1 = intervals[0][0]; 36 int pre2 = intervals[0][1]; 37 for (int i = 1; i < intervals.length; i++) { 38 if (pre2 >= intervals[i][0]) { 39 pre2 = Math.max(pre2, intervals[i][1]); 40 } else { 41 res.add(Arrays.asList(pre1, pre2)); 42 pre1 = intervals[i][0]; 43 pre2 = intervals[i][1]; 44 } 45 } 46 res.add(Arrays.asList(pre1, pre2)); 47 48 int[][] result = new int[res.size()][2]; 49 for (int i = 0; i < res.size(); i++) { 50 result[i][0] = res.get(i).get(0); 51 result[i][1] = res.get(i).get(1); 52 } 53 return result; 54 } 55} 56
3.复杂度分析
时间复杂度：O(nlogn).
空间复杂度：O(logn).
