建站网站平台,义乌网站备案,网页免费视频教程,相关网站怎么做都算是 重叠区间 问题#xff0c;大家可以好好感受一下。 都属于那种看起来好复杂#xff0c;但一看贪心解法#xff0c;惊呼#xff1a;这么巧妙#xff01; 还是属于那种#xff0c;做过了也就会了#xff0c;没做过就很难想出来。 不过大家把如下三题做了之后#… 都算是 重叠区间 问题大家可以好好感受一下。 都属于那种看起来好复杂但一看贪心解法惊呼这么巧妙 还是属于那种做过了也就会了没做过就很难想出来。 不过大家把如下三题做了之后 重叠区间 基本上差不多了 435. 无重叠区间 435. 无重叠区间 - 力扣LeetCode 我这里先给一下为什么不取最大值的问题吧我没看视频自己做的时候写的 如果用max的话就是直接计算重复区间了但是这道题还要删去所以直接取右边界的最小值 答案 这是我写的和卡哥的也不一样很简单 class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a,b)- {return Integer.compare(a[0],b[0]);});int count 0;for(int i 1;iintervals.length;i){if(intervals[i][0]intervals[i-1][1]){count;intervals[i][1] Math.min(intervals[i-1][1],intervals[i][1]);}}return count;}
} 763.划分字母区间 763. 划分字母区间 - 力扣LeetCode 题意难听卡哥讲easy很多。 class Solution {public ListInteger partitionLabels(String s) {int [] hash new int[27];//记录每个字母的最远位置for(int i 0;is.length();i){hash[s.charAt(i)-a] i; }ListInteger res new ArrayList();//找left和rightint left 0,right0;for(int i 0;is.length();i){right Math.max(right,hash[s.charAt(i)-a]);if(i right){res.add(right-left1);//更新边界left i1;}}return res;}
} 56. 合并区间 56. 合并区间 - 力扣LeetCode 这个很easy class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals,(a,b)-Integer.compare(a[0],b[0])); Listint[] res new ArrayList();int start intervals[0][0];int end intervals[0][1];for(int i 1;i intervals.length;i){if(intervals[i][0]end){//更新右边界end Math.max(end,intervals[i][1]);}else{//收集结果int [] subRes new int[]{start,end};res.add(subRes);//更新 新的begin 和endstart intervals[i][0];end intervals[i][1];}}res.add(new int[]{start,end});return res.toArray(new int[res.size()][]);}
}
