第三十六天 | 貪心算法 part05

435. 無重疊區(qū)間

題目鏈接/文字講解:無重疊區(qū)間

視頻講解:https://www.bilibili.com/video/BV1A14y1c7E1

題設(shè):給定一個區(qū)間的集合 intervals 抖拦,其中 intervals[i] = [starti, endi] 屡萤。返回 需要移除區(qū)間的最小數(shù)量,使剩余區(qū)間互不重疊 渊鞋。注意: 可以認為區(qū)間的終點總是大于它的起點。 區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”畔师,但沒有相互重疊范嘱。

思路:按照右邊界排序,從左向右記錄非交叉區(qū)間的個數(shù)瘦癌。最后用區(qū)間總數(shù)減去非交叉區(qū)間的個數(shù)就是需要移除的區(qū)間個數(shù)了,

20230201164134.png

按照左邊界排序的代碼:

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        int count = 0;
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        if (intervals.length == 0) return 0;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                count++;
                intervals[i][1] = Math.min(intervals[i][1], intervals[i - 1][1]);
            }
        }
        return count;
    }
}

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

題目鏈接/文字講解:劃分字母區(qū)間

視頻講解:https://www.bilibili.com/video/BV18G4y1K7d5

題設(shè):給你一個字符串 s 跷敬。我們要把這個字符串劃分為盡可能多的片段讯私,同一字母最多出現(xiàn)在一個片段中。

注意,劃分結(jié)果需要滿足:將所有劃分結(jié)果按順序連接妄帘,得到的字符串仍然是 s 楞黄。

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

思路:要找每一個字母的邊界抡驼,如果找到之前遍歷過的所有字母的最遠邊界鬼廓,說明這個邊界就是分割點了。

可以分為如下兩步:

  • 統(tǒng)計每一個字符最后出現(xiàn)的位置
  • 從頭遍歷字符致盟,并更新字符的最遠出現(xiàn)下標碎税,如果找到字符最遠出現(xiàn)位置下標和當前下標相等了,則找到了分割點馏锡。
20201222191924417.png

更新區(qū)間時雷蹂,left=i+1,right=max(right,當前字母右邊界)。

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();
        int[] edge = new int[26];
        for (int i = 0; i < s.length(); i++) {
            char letter = s.charAt(i);
            edge[letter - 'a'] = i;
        }
        int left = 0;
        int right = 0;
        for (int i = 0; i < s.length(); i++) {
            char letter = s.charAt(i);
            right = Math.max(right, edge[letter - 'a']);
            if (right == i) {
                list.add(right - left + 1);
                left = i + 1;
            }
        }
        return list;
    }
}

56. 合并區(qū)間

題目鏈接/文字講解:合并區(qū)間

視頻講解:https://www.bilibili.com/video/BV1wx4y157nD

題設(shè):以數(shù)組 intervals 表示若干個區(qū)間的集合杯道,其中單個區(qū)間為 intervals[i] = [starti, endi] 匪煌。請你合并所有重疊的區(qū)間,并返回 一個不重疊的區(qū)間數(shù)組党巾,該數(shù)組需恰好覆蓋輸入中的所有區(qū)間 萎庭。邊界重合可視為重合區(qū)間。

思路:按照左邊界從小到大排序之后齿拂,如果 intervals[i][0] <= intervals[i - 1][1] 即intervals[i]的左邊界 <= intervals[i - 1]的右邊界驳规,則一定有重疊。

20201223200632791.png

用合并區(qū)間后左邊界和右邊界署海,作為一個新的區(qū)間吗购,加入到result數(shù)組里就可以了。如果沒有合并就把原區(qū)間加入到result數(shù)組砸狞。

注意捻勉,在遍歷結(jié)束后還要添加一次,否則最后一個區(qū)間不能加入返回的result數(shù)組趾代。

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        int left = intervals[0][0];
        int right = intervals[0][1];
        List<int[]> res = new LinkedList<>();
        int index;
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= right) {
                right = Math.max(right, intervals[i][1]);
            } else {
                res.add(new int[]{left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        res.add(new int[]{left, right});
        return res.toArray(new int[res.size()][]);
    }
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末贯底,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子撒强,更是在濱河造成了極大的恐慌,老刑警劉巖笙什,帶你破解...
    沈念sama閱讀 223,002評論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件飘哨,死亡現(xiàn)場離奇詭異,居然都是意外死亡琐凭,警方通過查閱死者的電腦和手機芽隆,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評論 3 400
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人胚吁,你說我怎么就攤上這事牙躺。” “怎么了腕扶?”我有些...
    開封第一講書人閱讀 169,787評論 0 365
  • 文/不壞的土叔 我叫張陵孽拷,是天一觀的道長。 經(jīng)常有香客問我半抱,道長脓恕,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,237評論 1 300
  • 正文 為了忘掉前任窿侈,我火速辦了婚禮炼幔,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘史简。我一直安慰自己乃秀,他們只是感情好,可當我...
    茶點故事閱讀 69,237評論 6 398
  • 文/花漫 我一把揭開白布圆兵。 她就那樣靜靜地躺著环形,像睡著了一般。 火紅的嫁衣襯著肌膚如雪衙傀。 梳的紋絲不亂的頭發(fā)上抬吟,一...
    開封第一講書人閱讀 52,821評論 1 314
  • 那天,我揣著相機與錄音统抬,去河邊找鬼火本。 笑死,一個胖子當著我的面吹牛聪建,可吹牛的內(nèi)容都是我干的钙畔。 我是一名探鬼主播,決...
    沈念sama閱讀 41,236評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼金麸,長吁一口氣:“原來是場噩夢啊……” “哼擎析!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起挥下,我...
    開封第一講書人閱讀 40,196評論 0 277
  • 序言:老撾萬榮一對情侶失蹤揍魂,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后棚瘟,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體现斋,經(jīng)...
    沈念sama閱讀 46,716評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,794評論 3 343
  • 正文 我和宋清朗相戀三年偎蘸,在試婚紗的時候發(fā)現(xiàn)自己被綠了庄蹋。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片瞬内。...
    茶點故事閱讀 40,928評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖限书,靈堂內(nèi)的尸體忽然破棺而出虫蝶,到底是詐尸還是另有隱情,我是刑警寧澤倦西,帶...
    沈念sama閱讀 36,583評論 5 351
  • 正文 年R本政府宣布能真,位于F島的核電站,受9級特大地震影響调限,放射性物質(zhì)發(fā)生泄漏舟陆。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,264評論 3 336
  • 文/蒙蒙 一耻矮、第九天 我趴在偏房一處隱蔽的房頂上張望秦躯。 院中可真熱鬧,春花似錦裆装、人聲如沸踱承。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽茎活。三九已至,卻和暖如春琢唾,著一層夾襖步出監(jiān)牢的瞬間载荔,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評論 1 274
  • 我被黑心中介騙來泰國打工采桃, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留懒熙,地道東北人。 一個月前我還...
    沈念sama閱讀 49,378評論 3 379
  • 正文 我出身青樓普办,卻偏偏與公主長得像工扎,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子衔蹲,可洞房花燭夜當晚...
    茶點故事閱讀 45,937評論 2 361

推薦閱讀更多精彩內(nèi)容