[代码随机化第 30 天] 贪婪算法第 04 部分
最编程
2024-10-06 16:02:06
...
452. 用最少数量的箭引爆气球
题目链接/文章讲解:代码随想录
视频讲解:贪心算法,判断重叠区间问题 | LeetCode:452.用最少数量的箭引爆气球_哔哩哔哩_bilibili
class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, new Comparator<int[]>() {
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[0], o2[0]);
}
});
int count = 1;
for (int i = 1; i < points.length; i++) {
if (points[i][0] > points[i - 1][1]) {
count++;
} else {
points[i][1] = Math.min(points[i][1], points[i - 1][1]);
}
}
return count;
}
}
435. 无重叠区间
题目链接/文章讲解:代码随想录
视频讲解:贪心算法,依然是判断重叠区间 | LeetCode:435.无重叠区间_哔哩哔哩_bilibili
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, new Comparator<int[]>() {
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[0], o2[0]);
}
});
int count = 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.划分字母区间
题目链接/文章讲解:代码随想录
视频讲解:贪心算法,寻找最远的出现位置! LeetCode:763.划分字母区间_哔哩哔哩_bilibili
class Solution {
public List<Integer> partitionLabels(String s) {
int[] last = new int[26];
char[] charArray = s.toCharArray();
// 记录每个字符最后出现的位置
for (int i = 0; i < charArray.length; i++) {
last[charArray[i] - 'a'] = i;
}
List<Integer> list = new ArrayList<>();
int start = 0;
int end = 0;
for (int i = 0; i < charArray.length; i++) {
// 更新当前分区的结束位置
end = Math.max(end, last[charArray[i] - 'a']);
// 如果当前位置是分区的结束位置,则记录分区长度并更新 start
if (i == end) {
list.add(end - start + 1);
start = end + 1;
}
}
return list;
}
}
推荐阅读
-
[代码随机化第 30 天] 贪婪算法第 04 部分
-
代码随机化算法训练营第 41-2 天。买卖股票的最佳时机 II
-
代码随机化算法训练营第 32 天
-
代码随机化算法训练营第 24 天|77. combo
-
代码随机化算法训练营第 34 天 贪婪算法 3
-
代码随机化 - 算法训练营第 29 天 [回溯算法 05:递增后续,完全对齐]
-
代码随机化 - 算法训练营第 53 天 [动态程序设计 14:最长公共后序、不相连行、最大后序和(动态程序设计]
-
代码随机化训练营第 23 天:贪婪算法 1
-
代码随机化算法训练营第 56 天| 583. 删除两个字符串*, 72. 编辑距离*.
-
代码随机化算法训练营第 46 天 |139。分词 , cardcode.com 56。携带矿石资源