图片搜集网站怎么做,云南SEO网站建设,东营网约车最新消息,治疗男性性功能最好的医院435. 无重叠区间
我来按照右边界排序#xff0c;从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。图源#xff1a;代码随想录 class Solution {
public:// 按照区间右边界排序static bool cmp (const vectorint a…435. 无重叠区间
我来按照右边界排序从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。图源代码随想录 class Solution {
public:// 按照区间右边界排序static bool cmp (const vectorint a, const vectorint b) {return a[1] b[1];}int eraseOverlapIntervals(vectorvectorint intervals) {if (intervals.size() 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int count 1; // 记录非交叉区间的个数int end intervals[0][1]; // 记录区间分割点for (int i 1; i intervals.size(); i) {if (end intervals[i][0]) {end intervals[i][1];count;}}return intervals.size() - count;}
};
左边界排序也是可以的只不过 左边界排序我们就是直接求 重叠的区间count为记录重叠区间数
class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals,(a,b)-{return a[0]-b[0];});int count 0;for(int i1;iintervals.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;}
}
本题其实和452.用最少数量的箭引爆气球 (opens new window)非常像弓箭的数量就相当于是非交叉区间的数量只要把弓箭那道题目代码里射爆气球的判断条件加个等号认为[01][12]不是相邻区间然后用总区间数减去弓箭数量 就是要移除的区间数量了。 763.划分字母区间
统计每一个字符最后出现的位置从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点
图源代码随想录 class Solution {public ListInteger partitionLabels(String S) {ListInteger list new LinkedList();int[] edge new int[26];char[] chars S.toCharArray();for (int i 0; i chars.length; i) {edge[chars[i] - a] i;}int idx 0;int last -1;for (int i 0; i chars.length; i) {idx Math.max(idx,edge[chars[i] - a]);if (i idx) {list.add(i - last);last i;}}return list;}
}56. 合并区间
判断区间重叠问题
有重叠就合并区间
class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals,(a,b)-{return a[0]-b[0];});LinkedListint[] res new LinkedList();res.add(intervals[0]);for(int i1;iintervals.length;i){if(intervals[i][0]res.getLast()[1]){res.getLast()[1]Math.max(intervals[i][1],res.getLast()[1]);}else{res.add(intervals[i]);}}return res.toArray(new int[res.size()][]);}
}
