代码随想录刷题记录 day32无重叠区间 划分字母区间 合并区间

435. 无重叠区间

思想

其实要换个角度想，存放下尽可能多的区间，就是移除的最少的区间。可以按照左右边界进行排序。

1.如果按照右边界进行排序，从左往右遍历，选择右边界更小的，给下一个区间的空间更多，能存的就更多

2.遍历 判断当前的左边界是否比上一个的有边界大，不交叉，就count++；

得到的count是不重叠的区间的数量

代码

class Solution {public int eraseOverlapIntervals(int[][] intervals) {//1.按照右边界排序 从小到大Arrays.sort(intervals,(a,b)->{return a[1]-b[1];});for(int [] p:intervals){System.out.println(Arrays.toString(p));}//记录不重叠的区间int count=1;int minRight=intervals[0][1];//最小的右区间for(int i=1;iif(intervals[i][0]>=minRight){minRight=intervals[i][1];count++;}}return intervals.length- count;}
}

763. 划分字母区间

思想

属于是不看题解根本不会，看了题解第二天还是不会。

记录26个小写字母出现过的最大的下标，比如 ababc

s.charAt(i)-'a’找到的是字母对应的下标，

hash[s.charAt(i)-‘a’]=i 对下标赋值

left、right记录左右区间

遍历每一个字符，找到当前字符对应的最大的下标，如果当前字符的索引值等于最大下标，就做切割

代码

class Solution {public List partitionLabels(String s) {List res=new ArrayList<>();//每个字母只能出现在一个字段中int [] hash =new int[26];for(int i=0;ihash[s.charAt(i)-'a']=i;//统计每一个字符出现的最远的位置 随着i的增加 位置会变，s.charAt(i)-'a'是找到当前字母对应的下标}System.out.println(Arrays.toString(hash));int left=0;int right=0;for(int i=0;i//s.charAt(i)-'a'  找到当前字符对应的下标，比如a的下标//hash[s.charAt(i)-'a']  从hash中找到最远的距离right = Math.max(right,hash[s.charAt(i)-'a']);//if(i==right){res.add(right-left+1);left=i+1;}}return res;}
}

56. 合并区间

思想

1.按照左边界进行排序

2.遍历数组，不重叠加入结果集

3.重叠，记录最右的边界

代码

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals,(a,b)->{return a[0]-b[0];});List res=new ArrayList<>();//更新最大的右区间int maxRight=intervals[0][1];int left=intervals[0][0];for(int i=1;iif(intervals[i][0]>maxRight){//intervals[i][0]>intervals[i-1][1] 这样判断是有问题的 [1,10][2,3][4,5] i是往前遍历的 会判断 3是否大于4，但是实际上应该比较的是3是否大于10//不重叠res.add(new int[]{left,maxRight});left=intervals[i][0];maxRight=intervals[i][1];}else{//重叠了maxRight=Math.max(maxRight,intervals[i][1]);}}res.add(new int[]{left,maxRight});return res.toArray(new int[res.size()][]);}
}