435. 無重疊區(qū)間

思路

重疊問題都需要先排好序，再貪心

思路代碼

func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals,func(i,j int)bool{
        return intervals[i][1]<intervals[j][1]
    })
    count:=1
    end:=intervals[0][1]
    for i:=1;i<len(intervals);i++{
        if end<=intervals[i][0]{
            end=intervals[i][1]
            count++
        }
    }
    return len(intervals)-count
}

困難

搞清楚左右區(qū)間，重疊的條件。
要找出最少刪除的數(shù)量，也就是找出重疊空間的數(shù)量，然后用長度減去即可。

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

思路

這里提供一種與452.用最少數(shù)量的箭引爆氣球 (opens new window)、435.無重疊區(qū)間 (opens new window)相同的思路。

統(tǒng)計字符串中所有字符的起始和結(jié)束位置，記錄這些區(qū)間(實際上也就是435.無重疊區(qū)間 (opens new window)題目里的輸入)，將區(qū)間按左邊界從小到大排序，找到邊界將區(qū)間劃分成組，互不重疊。找到的邊界就是答案。

官方題解

一想到分割字符串就想到了回溯，但本題其實不用回溯去暴力搜索。

題目要求同一字母最多出現(xiàn)在一個片段中，那么如何把同一個字母的都圈在同一個區(qū)間里呢？

如果沒有接觸過這種題目的話，還挺有難度的。

在遍歷的過程中相當(dāng)于是要找每一個字母的邊界，如果找到之前遍歷過的所有字母的最遠邊界，說明這個邊界就是分割點了。此時前面出現(xiàn)過所有字母，最遠也就到這個邊界了。

可以分為如下兩步：

統(tǒng)計每一個字符最后出現(xiàn)的位置
從頭遍歷字符，并更新字符的最遠出現(xiàn)下標(biāo)，如果找到字符最遠出現(xiàn)位置下標(biāo)和當(dāng)前下標(biāo)相等了，則找到了分割點

代碼

func partitionLabels(s string) []int {
    var res []int;
    var marks [26]int;
    size, left, right := len(s), 0, 0;
    for i := 0; i < size; i++ {
        marks[s[i] - 'a'] = i;
    }
    for i := 0; i < size; i++ {
        right = max(right, marks[s[i] - 'a']);
        if i == right {
            res = append(res, right - left + 1);
            left = i + 1;
        }
    }
    return res;
}

func max(a, b int) int {
    if a < b {
        a = b;
    }
    return a;
}

困難

將字符串轉(zhuǎn)換為每個字符的起始位置，終止位置

56. 合并區(qū)間

思路

與前面類似但又不同

思路代碼

func merge(intervals [][]int) [][]int {
    res:=[][]int{}
    sort.Slice(intervals,func (i,j int)bool{
        return intervals[i][0]<intervals[j][0]})
    left,right:=intervals[0][0],intervals[0][1]
    for i:=1;i<len(intervals);i++{
        if right<intervals[i][0]{
            res=append(res,[]int{left,right})
            left=intervals[i][0]
            right=intervals[i][1]
        }else{
            right=max(right,intervals[i][1])
        }
    }
    res=append(res,[]int{left,right})
    return res

}

func max(i,j int)int{
    if i>j{
        return i
    }
    return j
}

今日收獲

重疊問題大致分兩類
一類是重疊區(qū)間問題（箭射氣球）
一類是合并區(qū)間問題
做法類似但是處理的邏輯不太相同，左右區(qū)間排序的選擇也有不同。文章來源地址http://www.zghlxwxcb.cn/news/detail-489413.html

到了這里，關(guān)于貪心算法part5 | ● 435. 無重疊區(qū)間 ● 763.劃分字母區(qū)間 ● 56. 合并區(qū)間的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！