代码随想录训练营Day36：● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间

本文主要是介绍代码随想录训练营Day36：● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

435. 无重叠区间

题目链接

https://leetcode.cn/problems/non-overlapping-intervals/description/

题目描述

在这里插入图片描述

思路

直接统计重叠区间的个数，就是需要删除的个数

在这里插入图片描述

public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals,(a,b)-> Integer.compare(a[0],b[0]));if(intervals.length == 0) return 0;int count = 0;for (int i = 1; i < intervals.length; i++) {//当前左区间小于上一个的右区间，就表明两个是互相重叠的if(intervals[i][0] < intervals[i-1][1]){count++;intervals[i][1] = Math.min(intervals[i][1],intervals[i-1][1]);}}return count;}

763.划分字母区间

题目链接

https://leetcode.cn/problems/partition-labels/description/

题目描述

在这里插入图片描述

思路

在这里插入图片描述
对于上边的字符串 s = “ababcbacadefegde”
最开始先包含 a ,根据题目要求，需要把所有的 a 都囊括进一个区间里边，所以找到最远的 a 为下标 8 的位置，但是在囊括 a 的同时，需要把 b c 囊括进来，所以需要再次找 b c 的最远位置，统计过 a b c 的最远位置之后进行比较，这一个区间的最远位置就是 8 ，因此 8 之前就为一个分割区间

class Solution {public List<Integer> partitionLabels(String s) {ArrayList<Integer> list = new ArrayList<>();//先统计每个字符出现的最远位置//遍历字符串int[] hash = new int[26];for (int i = 0; i < s.length(); i++) {hash[s.charAt(i) - 'a'] = i; }//定义区间的左右边界int left = 0,right = 0;for (int i = 0; i < s.length(); i++) {right = Math.max(right,hash[s.charAt(i) - 'a']);//i==right  说明已经到了这个字符串的最右边if(i==right){//将长度加到结果列表中list.add(right-left+1);left = i+1;}}return list;}
}

56. 合并区间

题目链接

https://leetcode.cn/problems/merge-intervals/description/

题目描述

在这里插入图片描述

思路

在这里插入图片描述
思路在代码注释中均有描述

public int[][] merge(int[][] intervals) {//存放最后的结果ArrayList<int[]> list = new ArrayList<>();if(intervals.length==0) return new int[0][];//按照左边界进行排序Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));list.add(intervals[0]);for (int i = 1; i < intervals.length; i++) {if(intervals[i][0] <= list.get(list.size()-1)[1]){//说明重叠了，需要进行合并//区间的最小边界肯定是已经存进去的左边界，所以不用做更新//需要更新右边界，将当前元素和已经存进去的右边界进行比较，取大的一方list.get(list.size()-1)[1] = Math.max(intervals[i][1],list.get(list.size()-1)[1]);}else {//没有重叠，直接添加到结果中，不做任何操作list.add(intervals[i]);}}return list.toArray(new int[list.size()][]);}