南希网站建设,windows优化大师怎么卸载,网页设计图片的边框怎么做,词典网站模板Day35题目
LeetCode435.无重叠区间:移除几个元素,使得不重叠
核心思想:排序区间之后,如果重叠,更新下一个区间的右边界为最小值.如果重叠了,最少移除其中一个,更新移除的那个为最小的右边界之后就不会影响到之后的区间判断
class Solution {public int eraseOverlapInterval…Day35题目
LeetCode435.无重叠区间:移除几个元素,使得不重叠
核心思想:排序区间之后,如果重叠,更新下一个区间的右边界为最小值.如果重叠了,最少移除其中一个,更新移除的那个为最小的右边界之后就不会影响到之后的区间判断
class Solution {public int eraseOverlapIntervals(int[][] intervals) {// 首先sort一下Arrays.sort(intervals,(a,b)-{return Integer.compare(a[0],b[0]);});int count 0;for(int i 1 ; i intervals.length ;i ){if(intervals[i-1][1] intervals[i][0]){intervals[i][1] Math.min(intervals[i][1],intervals[i-1][1]);count ;}}return count;}
}LeetCode763.划分字母
核心思想:获取字母的区间,然后如果遍历,遇到哪个字母右边界大于目前右边界,就更新遍历的终点.如果遍历到终点,说明这个区间内的所有包含的字母都只出现在目前这段区间内,我本来使用的map存储每一个区间,后面优化只用存储最后出现的地方就行了
class Solution {public ListInteger partitionLabels(String s) {int[] hash new int[27];ListInteger res new ArrayList();// 存储字母出现的最后一个位置for(int i 0 ; i s.length(); i ){hash[s.charAt(i)-a] i;}int start -1;int end hash[s.charAt(0)-a];for(int i 0; i s.length(); i ){if(hash[s.charAt(i)-a] end ){end hash[s.charAt(i)- a];}if(end i){res.add(i-start);start i;}}return res;}
}LeetCode56.合并区间:合并区间使得其中没有重叠或者相邻的区间
核心思想:排序后遍历,遇到相重叠的区间,将最小左边界到最大右边界存到结果集
class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals,(a,b)-{return a[0]-b[0];});Listint[] res new ArrayList();res.add(intervals[0]);for(int i 1 ; i intervals.length ; i ){if(res.getLast()[1] intervals[i][0] ){int[] temp new int[]{res.getLast()[0],Math.max(intervals[i][1],res.getLast()[1])};// 如果这个和上一个重叠了,那么把上一个移除,加入合并后的区间res.removeLast();res.add(temp);}else{res.add(intervals[i]);}}return res.toArray(new int[res.size()][]);}
}
