湖南做网站公司,南京设计公司前十名,重庆网站建设微信开发,国内seo公司哪家最好435. 无重叠区间
有了上题射气球的因子#xff0c;这题也就有思路了#xff0c;反正无脑排序就行了#xff1a;
首先将所有区间按照end的大小从小到大排序#xff1b;选取最早end为起始x_end遍历所有区间#xff0c;如果该区间的start比end大#xff08;可重叠#xf…435. 无重叠区间
有了上题射气球的因子这题也就有思路了反正无脑排序就行了
首先将所有区间按照end的大小从小到大排序选取最早end为起始x_end遍历所有区间如果该区间的start比end大可重叠说明不重叠count该区间的end重新定义为end
以上就是不重叠区间的用法用总区间数 - 不重叠区间数就是要删除的区间树
class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, Comparator.comparingInt(a - a[1]));int count 1;int x_end intervals[0][1];for(int[] point : intervals){if(point[0] x_end){//这里是等于因为顶点重叠不算重叠跟气球那题不一样count;x_end point[1];}}return intervals.length - count;}
}763. 划分字母区间
贪心就是找到每个字符最后出现的位置如果如果找到之前遍历过的所有字母的最远边界, 当前i等于边界就加入结果集再把left 1:
class Solution {private int[] alphabet new int[26];private ListInteger resList new ArrayList();public ListInteger partitionLabels(String s) {for(int i 0 ; i s.length(); i){alphabet[s.charAt(i) - a] i;}int left 0, right 0;for(int i 0; i s.length(); i){right Math.max(right, alphabet[s.charAt(i) - a]);if(i right){resList.add(i - left 1);left i 1;}}return resList;}}初始化一个右边界right是i之前所有字母的最远边界的最大值左边界left用于计算区间长度。
56. 合并区间
这题的关键点在于通过更新resList中的元素特别是终点end而不是创建新元素直接加入。
class Solution {public int[][] merge(int[][] intervals) {LinkedListint[] res new LinkedList();Arrays.sort(intervals, Comparator.comparingInt(o - o[0]));res.add(intervals[0]);for (int i 1; i intervals.length; i) {if (intervals[i][0] res.getLast()[1]) {int start res.getLast()[0];int end Math.max(intervals[i][1], res.getLast()[1]);//实际上就是更新res的最后一个元素res.removeLast();res.add(new int[]{start, end});}else {res.add(intervals[i]);}}return res.toArray(new int[res.size()][]);}
}
