网上做任务网站有哪些内容,创意个人网页设计,百度账号注册入口,苏州归巢网络科技有限公司一、无重叠区间
力扣第435题
第一种方法#xff1a;
个人思路#xff1a; 按照区间左边界排序#xff0c;然后从左开始遍历#xff0c;每遍历到一个区间就要保证该区间之前的集合为不重叠区间#xff08;贪心#xff0c;局部最优解#xff09;。 难点在于如何把新遍历…一、无重叠区间
力扣第435题
第一种方法
个人思路 按照区间左边界排序然后从左开始遍历每遍历到一个区间就要保证该区间之前的集合为不重叠区间贪心局部最优解。 难点在于如何把新遍历到的区间整合为不重叠分情况讨论。
代码如下
class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a, b) - {if(a[0] b[0]) return a[1] - b[1];return a[0] - b[0];});int remove 0;for(int i 1; i intervals.length; i) {if(intervals[i][0] intervals[i - 1][0]) {if(intervals[i][1] intervals[i - 1][1]) {intervals[i][1] intervals[i - 1][1];}remove ;} else if(intervals[i][0] intervals[i - 1][1]) {if(intervals[i][1] intervals[i - 1][1]) {intervals[i][0] intervals[i - 1][0];intervals[i][1] intervals[i - 1][1];}remove ;}}return remove;}
}
时间复杂度O(nlogn)
空间复杂度O(1)
第二种方法
思路 统计不重叠区间最后区间总和减去不重叠区间个数就等于重叠区间个数。
代码如下
class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a,b)- {return Integer.compare(a[0],b[0]);});int count 1;for(int i 1;i intervals.length;i){if(intervals[i][0] intervals[i-1][1]){intervals[i][1] Math.min(intervals[i - 1][1], intervals[i][1]);continue;}else{count;} }return intervals.length - count;}
}
时间复杂度O(nlogn)
空间复杂度O(1)
二、划分字母区间
力扣第763题
思路 在遍历的过程中相当于是要找每一个字母的边界如果找到之前遍历过的所有字母的最远边界说明这个边界就是分割点了。此时前面出现过所有字母最远也就到这个边界了。 可以分为如下两步
统计每一个字符最后出现的位置从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点
代码如下
class Solution {public ListInteger partitionLabels(String s) {int[] hash new int[27];for(int i 0; i s.length(); i) {char c s.charAt(i);hash[c - a] i;}ListInteger list new ArrayList();int left 0;int right 0;for(int i 0; i s.length(); i) {right Math.max(right, hash[s.charAt(i) - a]);if(i right) {list.add(right - left 1);left i 1;}}return list;}
}
时间复杂度:O(n)
空间复杂度:O(1)
三、合并区间
力扣第56题
代码如下
class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (a, b) - {if(a[0] b[0]) return a[1] - b[1];return a[0] - b[0];});Listint[] list new ArrayList();list.add(intervals[0]);int index 0;for(int i 1; i intervals.length; i) {if(intervals[i][0] list.get(index)[1]) {list.get(index)[1] Math.max(intervals[i][1], list.get(index)[1]);} else {list.add(intervals[i]);index;}}return list.toArray(new int[list.size()][]);}
}
时间复杂度O(nlogn);
空间复杂度O(1);
