代码随想录算法训练营第三十六天| 435. 无重叠区间、 763.划分字母区间、56. 合并区间

435

题目：

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

题目链接：435. 无重叠区间 - 力扣（LeetCode）

思路：

先按起始位置升序排列，然后判断是否有重合，如果重合就count+1,然后判断哪个区间的end更大，两个区间肯定要删除一个，end更大的容易和后续重合故删。

详情：代码随想录 (programmercarl.com)

代码：

class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));int count = 0;for(int i=1;i<intervals.length;i++){if(intervals[i][0]>=intervals[i-1][1])continue;else{count++;if(intervals[i-1][1]<=intervals[i][1]) //i的终止位置大，更容易影响后续故删{intervals[i][0]=intervals[i-1][0];intervals[i][1]=intervals[i-1][1];}else{//i-1的终止位置大，更容易影响后续故删intervals[i-1][0]=intervals[i][0];intervals[i-1][1]=intervals[i][1];                   }}}return count;}
}

763

题目：

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

题目链接：763. 划分字母区间 - 力扣（LeetCode）

思路：

使用for循环，在其中判断当前对应的字符在字符串最后一次出现下标，在这个下标之前的所有字符都要计算lastindexof，当i==index则是一个分段。

详情：代码随想录 (programmercarl.com)

代码：

class Solution {public List<Integer> partitionLabels(String s) {List <Integer> len =new ArrayList<Integer>(); int index =-1;//片段的endint flag=0;//辅助标识片段startint start=-1;for(int i=0;i<s.length();i++){if(flag==0) {start=i;flag=1;}String str =Character.toString(s.charAt(i));int last =s.lastIndexOf(str);if(last > index)index = last;if(i==index)    {int temp =index-start+1;len.add(temp);flag =0;start=-1;index =-1;}}return len;}
}

56

题目：

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

题目链接：56. 合并区间 - 力扣（LeetCode）

思路：

先判断前者和后者是否有交集，有的话将合并的结果存在后者，然后另开一个动态数组存储结果，只需要存合并后的区间和不相交的区间。

详情：代码随想录 (programmercarl.com)

代码：

class Solution {public int[][] merge(int[][] intervals) {int index = intervals.length - 1;//为了处理24行的边界情况if(index==0) return intervals;//只有一个区间Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));//按start升序排序for (int i = 1; i < index + 1; i++) { //有交集则将i-1和i的区间合并存储到i里if (intervals[i][0] > intervals[i - 1][1])continue;else {intervals[i][0] = Math.min(intervals[i - 1][0],intervals[i][0]);intervals[i][1] = Math.max(intervals[i-1][1],intervals[i][1]);}}LinkedList<int[]> que = new LinkedList<>();int count = 0;for (int i = 0; i < index; i++) { //判断前者是否是后者子区间，如果是则继续，如果不是则保存if (intervals[i][0] >= intervals[i + 1][0] && intervals[i][1] <= intervals[i + 1][1])continue;else {que.add(intervals[i]);count++;}}//边界情况if (intervals[index - 1][0] >= intervals[index][0] && intervals[index - 1][1] <= intervals[index][1]) {que.add(intervals[index]);count++;} else {que.add(intervals[index]);count = count + 1;}return que.toArray(new int[count][]);}
}