代碼隨想錄-035期-算法訓練營【博客筆記匯總表】-CSDN博客

第八章 貪心算法 part05● 435. 無重疊區間 
● 763.劃分字母區間 
● 56. 合并區間 詳細布置  今天的三道題目，都算是 重疊區間 問題，大家可以好好感受一下。 都屬于那種看起來好復雜，但一看貪心解法，驚呼：這么巧妙！ 
還是屬于那種，做過了也就會了，沒做過就很難想出來。
不過大家把如下三題做了之后， 重疊區間 基本上差不多了435. 無重疊區間 https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html  763.劃分字母區間 https://programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html  56. 合并區間  
本題相對來說就比較難了。https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html  往日任務
● day 1 任務以及具體安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY  
● day 2 任務以及具體安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG  
● day 3 任務以及具體安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6 
● day 4 任務以及具體安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp 
● day 5 周日休息
● day 6 任務以及具體安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4 
● day 7 任務以及具體安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj 
● day 8 任務以及具體安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH 
● day 9 任務以及具體安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4 
● day 10 任務以及具體安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q 
●day 11 任務以及具體安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0 
●day 12 周日休息 
●day 13 任務以及具體安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3 
●day 14 任務以及具體安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE 
●day 15 任務以及具體安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv 
●day 16 任務以及具體安排：https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK 
●day 17 任務以及具體安排：https://docs.qq.com/doc/DUFpXY3hBZkpabWFY 
●day 18 任務以及具體安排：https://docs.qq.com/doc/DUFFiVHl3YVlReVlr 
●day 19 周日休息
●day 20 任務以及具體安排：https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH  
●day 21 任務以及具體安排：https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X 
●day 22 任務以及具體安排：https://docs.qq.com/doc/DUHplVUp5YnN1bnBL  
●day 23 任務以及具體安排：https://docs.qq.com/doc/DUFBUQmxpQU1pa29C 
●day 24 任務以及具體安排：https://docs.qq.com/doc/DUEhsb0pUUm1WT2NP  
●day 25 任務以及具體安排：https://docs.qq.com/doc/DUExTYXVzU1BiU2Zl 
●day 26 休息 
●day 27 任務以及具體安排：https://docs.qq.com/doc/DUElpbnNUR3hIbXlY 
●day 28 任務以及具體安排：https://docs.qq.com/doc/DUG1yVHdlWEdNYlhZ  
●day 29 任務以及具體安排：https://docs.qq.com/doc/DUHZYbWhwSHRCRmp3 
●day 30 任務以及具體安排：https://docs.qq.com/doc/DUEdTVVhxbnJiY3BR 
●day 31 任務以及具體安排：https://docs.qq.com/doc/DUG1PQ1ZZY2xXY1ly 
●day 32 任務以及具體安排：https://docs.qq.com/doc/DUGFEdGFWeVhleFF1 
●day 33 周日休息 
●day 34 任務以及具體安排：https://docs.qq.com/doc/DUEh5WFVlQkp1U0p4  
●day 35 任務以及具體安排：https://docs.qq.com/doc/DUFRWc3BGRHFXZ1pO

目錄

0435_無重疊區間

0763_劃分字母區間

0056_合并區間

---

0435_無重疊區間

package com.question.solve.leetcode.programmerCarl2._09_greedyAlgorithms;import java.util.Arrays;public class _0435_無重疊區間 {
}class Solution0435 {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a, b) -> {return Integer.compare(a[0], b[0]);});int count = 1;for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] < intervals[i - 1][1]) {intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);continue;} else {count++;}}return intervals.length - count;}
}class Solution0435_2 {//按左邊排序，不管右邊順序。相交的時候取最小的右邊。public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a, b) -> {return Integer.compare(a[0], b[0]);});int remove = 0;int pre = intervals[0][1];for (int i = 1; i < intervals.length; i++) {if (pre > intervals[i][0]) {remove++;pre = Math.min(pre, intervals[i][1]);} else pre = intervals[i][1];}return remove;}
}

0763_劃分字母區間

package com.question.solve.leetcode.programmerCarl2._09_greedyAlgorithms;import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;public class _0763_劃分字母區間 {
}class Solution0763 {public List<Integer> partitionLabels(String s) {List<Integer> list = new LinkedList<>();int[] edge = new int[26];char[] chars = s.toCharArray();for (int i = 0; i < chars.length; i++) {edge[chars[i] - 'a'] = i;}int idx = 0;int last = -1;for (int i = 0; i < chars.length; i++) {idx = Math.max(idx, edge[chars[i] - 'a']);if (i == idx) {list.add(i - last);last = i;}}return list;}
}class Solution0763_2 {/*解法二： 上述c++補充思路的Java代碼實現*/public int[][] findPartitions(String s) {List<Integer> temp = new ArrayList<>();int[][] hash = new int[26][2];//26個字母2列 表示該字母對應的區間for (int i = 0; i < s.length(); i++) {//更新字符c對應的位置ichar c = s.charAt(i);if (hash[c - 'a'][0] == 0) hash[c - 'a'][0] = i;hash[c - 'a'][1] = i;//第一個元素區別對待一下hash[s.charAt(0) - 'a'][0] = 0;}List<List<Integer>> h = new LinkedList<>();//組裝區間for (int i = 0; i < 26; i++) {//if (hash[i][0] != hash[i][1]) {temp.clear();temp.add(hash[i][0]);temp.add(hash[i][1]);//System.out.println(temp);h.add(new ArrayList<>(temp));// }}// System.out.println(h);// System.out.println(h.size());int[][] res = new int[h.size()][2];for (int i = 0; i < h.size(); i++) {List<Integer> list = h.get(i);res[i][0] = list.get(0);res[i][1] = list.get(1);}return res;}public List<Integer> partitionLabels(String s) {int[][] partitions = findPartitions(s);List<Integer> res = new ArrayList<>();Arrays.sort(partitions, (o1, o2) -> Integer.compare(o1[0], o2[0]));int right = partitions[0][1];int left = 0;for (int i = 0; i < partitions.length; i++) {if (partitions[i][0] > right) {//左邊界大于右邊界即可記為一次分割res.add(right - left + 1);left = partitions[i][0];}right = Math.max(right, partitions[i][1]);}//最右端res.add(right - left + 1);return res;}
}

0056_合并區間

package com.question.solve.leetcode.programmerCarl2._09_greedyAlgorithms;import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;public class _0056_合并區間 {
}/*** 時間復雜度：O(NlogN) 排序需要 O(NlogN)* 空間復雜度：O(logN)  java的內置排序是快速排序，需要 O(logN) 空間*/
class Solution0056 {public int[][] merge(int[][] intervals) {List<int[]> res = new LinkedList<>();//按照左邊界排序Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));//initial start 是最小左邊界int start = intervals[0][0];int rightmostRightBound = intervals[0][1];for (int i = 1; i < intervals.length; i++) {//如果左邊界大于最大右邊界if (intervals[i][0] > rightmostRightBound) {//加入區間 并且更新startres.add(new int[]{start, rightmostRightBound});start = intervals[i][0];rightmostRightBound = intervals[i][1];} else {//更新最大右邊界rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);}}res.add(new int[]{start, rightmostRightBound});return res.toArray(new int[res.size()][]);}
}class Solution0056_2 {//版本2public int[][] merge(int[][] intervals) {LinkedList<int[]> res = new LinkedList<>();Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));res.add(intervals[0]);for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] <= res.getLast()[1]) {int start = res.getLast()[0];int end = Math.max(intervals[i][1], res.getLast()[1]);res.removeLast();res.add(new int[]{start, end});} else {res.add(intervals[i]);}}return res.toArray(new int[res.size()][]);}
}