【贪心算法part05】| 435.无重叠区间、763.划分字母区间、56.合并区间-Toy模板网

这篇具有很好参考价值的文章主要介绍了【贪心算法part05】| 435.无重叠区间、763.划分字母区间、56.合并区间。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🎈LeetCode435. 无重叠区间

🎈LeetCode763.划分字母区间

🎈LeetCode 56.合并区间

🎈LeetCode435. 无重叠区间

链接：435.无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

【贪心算法part05】| 435.无重叠区间、763.划分字母区间、56.合并区间,贪心算法,算法

public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
        int result=0;
        for(int i=1;i<intervals.length;i++){
            if(intervals[i][0]<intervals[i-1][1]){
                result++; 
                intervals[i][1]=Math.min(intervals[i][1],intervals[i-1][1]);
            }
        }
        return result;
    }

🎈LeetCode763.划分字母区间

链接：763.划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

【贪心算法part05】| 435.无重叠区间、763.划分字母区间、56.合并区间,贪心算法,算法

ublic List<Integer> partitionLabels(String s) {
        List<Integer> result=new ArrayList<>();
        int[] hash=new int[30];
        // 找每个字母出现的最远距离
        for(int i=0;i<s.length();i++){
            hash[s.charAt(i)-'a']=i;
        }
        int left=0;
        int right=0;
        for(int i=0;i<s.length();i++){
            right=Math.max(right,hash[s.charAt(i)-'a']);
            if(right==i){
                result.add(right-left+1);
                left=right+1;
            }
        }
        return result;
    }

🎈LeetCode 56.合并区间

链接：56.合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

【贪心算法part05】| 435.无重叠区间、763.划分字母区间、56.合并区间,贪心算法,算法文章来源地址https://www.toymoban.com/news/detail-601724.html

public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->(a[0]-b[0]));
        ArrayList<int[]> list=new ArrayList<>();
        int start=intervals[0][0];
        for(int i=1;i<intervals.length;i++){
            if(intervals[i][0]<=intervals[i-1][1]){
                intervals[i][1]=Math.max(intervals[i][1],intervals[i-1][1]);
            }else{
                list.add(new int[]{start,intervals[i-1][1]});
                start=intervals[i][0];
            }
        }
        list.add(new int[]{start,intervals[intervals.length-1][1]});
        return list.toArray(new int[list.size()][]);
    }

到了这里，关于【贪心算法part05】| 435.无重叠区间、763.划分字母区间、56.合并区间的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！