目錄

??LeetCode435.?無重疊區(qū)間?

???LeetCode763.劃分字母區(qū)間

??LeetCode 56.合并區(qū)間

??LeetCode435.?無重疊區(qū)間?

鏈接：435.無重疊區(qū)間

給定一個區(qū)間的集合?intervals?，其中?intervals[i] = [starti, endi]?。返回?需要移除區(qū)間的最小數量，使剩余區(qū)間互不重疊?。?

?

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.劃分字母區(qū)間

鏈接：763.劃分字母區(qū)間

給你一個字符串?s?。我們要把這個字符串劃分為盡可能多的片段，同一字母最多出現在一個片段中。

注意，劃分結果需要滿足：將所有劃分結果按順序連接，得到的字符串仍然是?s?。

返回一個表示每個字符串片段的長度的列表。

?

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.合并區(qū)間

鏈接：56.合并區(qū)間

以數組?intervals?表示若干個區(qū)間的集合，其中單個區(qū)間為?intervals[i] = [starti, endi]?。請你合并所有重疊的區(qū)間，并返回?一個不重疊的區(qū)間數組，該數組需恰好覆蓋輸入中的所有區(qū)間?。?

?文章來源地址http://www.zghlxwxcb.cn/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.無重疊區(qū)間、763.劃分字母區(qū)間、56.合并區(qū)間的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！