第八章 貪心算法 part04
今天的三道題目，都算是 重疊區(qū)間 問(wèn)題喳逛，大家可以好好感受一下瞧捌。 都屬于那種看起來(lái)好復(fù)雜，但一看貪心解法润文，驚呼：這么巧妙姐呐！
這種題還是屬于那種，做過(guò)了也就會(huì)了典蝌，沒(méi)做過(guò)就很難想出來(lái)曙砂。
不過(guò)大家把如下三題做了之后， 重疊區(qū)間 基本上差不多了
452. 用最少數(shù)量的箭引爆氣球
思路
- 存在重疊的氣球就一起射
- 不用移除氣球數(shù)組的元素骏掀，只需要統(tǒng)計(jì)箭的數(shù)量
- 將數(shù)組按照起始位置排序鸠澈，如果氣球重疊了，那么右邊邊界的最小值
- 算法步驟
- 排序：
首先按氣球的結(jié)束位置（points[i][1]）對(duì)所有氣球進(jìn)行排序截驮。這是因?yàn)槲覀兿ＭM可能長(zhǎng)地利用每支箭的有效范圍笑陈。 - 初始化：
我們至少需要一支箭，所以初始化 arrows = 1葵袭。
end 用來(lái)記錄當(dāng)前箭的有效射程的結(jié)束位置涵妥，初始為第一個(gè)氣球的結(jié)束位置 points[0][1]。 - 遍歷氣球：
從第二個(gè)氣球開(kāi)始坡锡，逐個(gè)檢查氣球蓬网。
如果當(dāng)前氣球的起始位置 points[i][0] 大于 end，這意味著當(dāng)前氣球與之前的氣球不重疊鹉勒，需要新增一支箭帆锋。
如果當(dāng)前氣球與之前的氣球重疊（即 points[i][0] <= end），它們可以共享同一支箭贸弥。
- 排序：
class Solution {
public int findMinArrowShots(int[][] points) {
//按照結(jié)束位置從小到大排序
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
int result = 1;
for(int i = 1; i < points.length; i++){
// 氣球 i 的起始位置 points[i][0] 大于前一個(gè)氣球 i-1 的結(jié)束位置 points[i - 1][1]窟坐，說(shuō)明這兩個(gè)氣球不重疊，也不相鄰。
if(points[i][0] > points[i-1][1]){
result++;
}else{
//注意這里的邏輯是更新氣球最小右邊界
points[i][1] = Math.min(points[i][1], points[i-1][1]);
}
}
return result;
}
}
435. 無(wú)重疊區(qū)間
思路
- 按照右邊界排序哲鸳，從左向右記錄非交叉區(qū)間的個(gè)數(shù)臣疑。最后用區(qū)間總數(shù)減去非交叉區(qū)間的個(gè)數(shù)就是需要移除的區(qū)間個(gè)數(shù)了。
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
int count = 1;
int end = intervals[0][1];
for(int i = 1; i < intervals.length; i++){
if(end <= intervals[i][0]){
end = intervals[i][1];
count++;
}
}
return intervals.length - count;
}
}
763.劃分字母區(qū)間
思路
- 解法1：
1.統(tǒng)計(jì)每一個(gè)字符最后出現(xiàn)的位置
2.從頭遍歷字符徙菠，并更新字符的最遠(yuǎn)出現(xiàn)下標(biāo)讯沈，如果找到字符最遠(yuǎn)出現(xiàn)位置下標(biāo)和當(dāng)前下標(biāo)相等了，則找到了分割點(diǎn) - 解法2：
將區(qū)間按左邊界從小到大排序婿奔，找到邊界將區(qū)間劃分成組缺狠，互不重疊。找到的邊界就是答案萍摊。
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> result = new LinkedList<>();
int[] edge = new int[26];
char[] chars = s.toCharArray();
for(int i = 0; i < chars.length; i++){
edge[chars[i] - 'a'] = i;//如：edge[0] = 2挤茄，表示字符 'a' 最后出現(xiàn)的位置是索引 2。
}
int left = 0;
int right = 0;
for(int i = 0; i < s.length(); i++){
// 更新最遠(yuǎn)邊界 right：因?yàn)閷?duì)于每個(gè)字符 chars[i]冰木，edge[chars[i] - 'a'] 給出了該字符的最后出現(xiàn)位置穷劈。
// right = Math.max(right, edge[chars[i]-'a'])
// 這一行代碼確保 idx 始終表示從當(dāng)前字符到目前為止，所有字符的最遠(yuǎn)邊界踊沸。
right = Math.max(right, edge[chars[i]-'a']);
if(i == right){
result.add(right - left + 1);
left = i + 1;
}
}
return result;
}
}
只寫(xiě)了第一種歇终，有時(shí)間寫(xiě)第二種
