452. 擊破氣球的最少箭數
有些球形氣球貼在代表 XY 平面的平坦牆壁上。氣球表示為 2D 整數數組點，其中，points[i] = [xstart, xend] 表示水平直徑在 xstart 和 xend 之間延伸的氣球。您不知道氣球的確切 y 座標。
箭頭可以從沿著 x 軸的不同點直接垂直（沿 y 軸正方向）射出。如果 xstart
給定數組點，返回擊破所有氣球所需的最少箭數。
範例1：
輸入：points = [[10,16],[2,8],[1,6],[7,12]]
輸出：2
說明：氣球可以用 2 個箭頭爆破：
- 在 x = 6 處射箭，使氣球 [2,8] 和 [1,6] 破裂。
- 在 x = 11 處射箭，使氣球 [10,16] 和 [7,12] 破裂。
範例2：
輸入：points = [[1,2],[3,4],[5,6],[7,8]]
輸出：4
說明：每個氣球需要射一支箭，總共4支箭。
範例 3：
輸入：points = [[1,2],[2,3],[3,4],[4,5]]
輸出：2
說明：氣球可以用 2 個箭頭爆破：
- 在 x = 2 處射箭，使氣球 [1,2] 和 [2,3] 破裂。
- 在 x = 4 處射箭，使氣球 [3,4] 和 [4,5] 破裂。
限制：
1
點[i].length == 2
-2^31
原始頁
public int findMinArrowShots(int[][] points) {
if(points.length == 0){
return 0;
}
Arrays.sort(points, (a,b) ->{
if(a[0] == b[0]){
return a[1] - b[1];
}
return a[0] - b[0];
});
int arrow = 1;
int start = points[0][0];
int end = points[0][1];
for(int i=0; i<points.length; i++){
if((points[i][0] >= start && points[i][0]<= end) ||
(end >=points[i][0] && end <= points[i][1])){
//Narrow the arrow point down
if(points[i][0] > start && points[i][0] <= end){
start = points[i][0];
}
if(points[i][1]>start && points[i][1] < end){
end = points[i][1];
}
continue;
}else{
// current arrow point is not satisfied with balloons
start = points[i][0];
end = points[i][1];
arrow ++;
}
}
return arrow;
}
登入後複製
435. 不重疊的區間
給定一個間隔數組，其中間隔[i] = [starti, endi]，傳回需要刪除的最小間隔數，以使其餘間隔不重疊。
範例1：
輸入：間隔 = [[1,2],[2,3],[3,4],[1,3]]
輸出：1
解釋：[1,3]可以去掉，其餘區間不重疊。
範例2：
輸入：間隔 = [[1,2],[1,2],[1,2]]
輸出：2
解釋：您需要刪除兩個 [1,2] 以使其餘間隔不重疊。
範例 3：
輸入：間隔 = [[1,2],[2,3]]
輸出：0
說明：您不需要刪除任何間隔，因為它們已經不重疊。
限制：
1 <= 間隔.長度 <= 10^5
間隔[i].length == 2
-5 * 10^4 <= 起始 <結束 <= 5 * 10^4
原始頁
錯誤代碼
public int eraseOverlapIntervals(int[][] intervals) {
if(intervals.length == 0){
return 0;
}
Arrays.sort(intervals, (a,b) ->{
if(a[0] == b[0]){
return a[1] - b[1];
}
return a[0] - b[0];
});
Arrays.stream(intervals)
.map(Arrays::toString)
.forEach(System.out::println);
int count = 0;
// List<int[]> list = new LinkedList<>();
int start = intervals[0][0];
int end = intervals[0][1];
for(int i=1; i<intervals.length; i++){
//if the left edge is not included in the previous interval the right will definitely not be in it.
if(intervals[i][0] >=start && intervals[i][0] <end){
count++;
continue;
}
start = intervals[i][0];
end = intervals[i][1];
// list.add(intervals[i]);
}
return count;
}
登入後複製
修復它
public int eraseOverlapIntervals(int[][] intervals) {
if(intervals.length == 0){
return 0;
}
Arrays.sort(intervals, (a,b) ->{
return a[0] - b[0];
});
int count = 0;
int start = intervals[0][0];
int end = intervals[0][1];
for(int i=1; i<intervals.length; i++){
if(intervals[i][0] < intervals[i-1][1]){
count++;
// here we need to find the maximum overlap, the means whether the next element overlap to above groups of overlaps
// if only find overlap from the previous interval, it may cause miss calculation over-add 1 count
intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);
}
}
return count;
}
登入後複製
763. 分區標籤
給你一個字串 s。我們希望將字串分成盡可能多的部分，以便每個字母最多出現在一個部分中。
請注意，分割區的完成是為了將所有部分依序連接後，得到的字串應該是 s。
傳回表示這些部分大小的整數清單。
範例1：
輸入：s = "ababcbacadefegdehijhklij"
輸出：[9,7,8]
說明：
分區是“ababcbaca”、“defegde”、“hijhklij”。
這是一個分區，以便每個字母最多出現在一個部分。
像“ababcbacadefegde”、“hijhklij”這樣的分區是不正確的，因為它將 s 分成更少的部分。
範例2：
輸入：s = "eccbbbbdec"
輸出：[10]
限制：
1 <= s.length <= 500
s 由小寫英文字母組成。
原始頁
public List<Integer> partitionLabels(String s) {
List<Integer> list = new ArrayList<>();
Set<Character> set = new HashSet<>();
if(s.length() == 0){
return list;
}
int start = 0;
int end = 0;
for(int i=0; i<s.length(); i++){
Character target = s.charAt(i);
if(!set.contains(target)){
set.add(target);
int j = s.length()-1;
for(;j>i;j--){
if(s.charAt(j) == target){
break;
}
}
end = Math.max(end, j);
}
if(i == end){
list.add(end-start+1);
start = i+1;
set.clear();
}
}
return list;
}
登入後複製
public List<Integer> partitionLabels(String s) {
List<Integer> list = new ArrayList<>();
Set<Character> set = new HashSet<>();
int[] pos = new int[27];
for(int i=s.length()-1; i>0;i--){
if(pos[s.charAt(i)-'a'] == 0){
pos[s.charAt(i)-'a'] = i;
}
}
if(s.length() == 0){
return list;
}
int start = 0;
int end = 0;
for(int i=0; i<s.length(); i++){
Character target = s.charAt(i);
if(!set.contains(target)){
set.add(target);
end = Math.max(end, pos[target-'a']);
}
if(i == end){
list.add(end-start+1);
start = i+1;
set.clear();
}
}
return list;
}
登入後複製
public List<Integer> partitionLabels(String s) {
List<Integer> list = new ArrayList<>();
int[] pos = new int[27];
for(int i=s.length()-1; i>0;i--){
if(pos[s.charAt(i)-'a'] == 0){
pos[s.charAt(i)-'a'] = i;
}
}
if(s.length() == 0){
return list;
}
int start = 0;
int end = 0;
for(int i=0; i<s.length(); i++){
Character target = s.charAt(i);
end = Math.max(end, pos[target-'a']);
if(i == end){
list.add(end-start+1);
start = i+1;
}
}
return list;
}
登入後複製
因為判斷元素是否已經在集合中並不重要，所以我們只關注是否到達終點，如果出現相同的元素，則終點不會改變，如果不同的元素合併，看起來end 可能會改變，但所有這些都不會影響if 評估，因此我們可以刪除它們。
以上是LeetCode Day 貪心演算法 第 4 部分的詳細內容。更多資訊請關注PHP中文網其他相關文章！
