第三十天|贪婪算法| 452. 用最少数量的箭引爆气球，435. 无重叠区间 ，763.
目录452. 用最少数量的箭引爆气球
435. 无重叠区间
763.划分字母区间
本日的题目都算是 重叠区间 题目。
452. 用最少数量的箭引爆气球
为了让气球尽大概的重叠，必要对数组举行排序。
假如气球重叠了，重叠气球中右边边界的最小值 之前的区间肯定必要一个弓箭。
https://i-blog.csdnimg.cn/direct/7de6a0914ceb423bba6bce5ad58351e2.png
class Solution {
public int findMinArrowShots(int[][] points) {
// Arrays.sort(points, (a, b) -> {
// if (a == b) {
// return Integer.compare(a, b);
// }
// return Integer.compare(a, b);
// });
Arrays.sort(points, (a, b) -> Integer.compare(a, b));
int count = 1; // points 不为空至少需要一支箭
for (int i = 1; i < points.length; i++) {
if (points > points) {
count++;
} else {
points = Math.min(points, points); // 更新重叠气球最小右边界
}
}
return count;
}
}
[*]时间复杂度：O(nlog n)，排序必要 O(NlogN) 的复杂度
[*]空间复杂度：O( log n)，java所利用的内置函数用的是快速排序必要 logN 的空间
留意，排序这块必要用 Integer.compare(a, b)
由于一开始我用的是：
if (a == b) {
return a - b;
}
return a - b;
当数组包含极大或极小的整数（如 Integer.MIN_VALUE 和 Integer.MAX_VALUE）时，直接利用减法盘算差值大概导致 整数溢出，则会产生溢出错误。
为了制止溢出，可以利用 Integer.compare 方法代替减法，由于它可以安全地比较两个整数而不会产生溢出。Integer.compare(a, b)：会返回一个负值、零或正值，分别表示 a 小于、即是或大于 b。
435. 无重叠区间
按左边排序，不管右边次序。相交的时候取最小的右边。
与452很类似，简朴。
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 1) {
return 0;
}
Arrays.sort(intervals,(a,b)->Integer.compare(a,b));
int count = 0;
for (int i = 1; i < intervals.length; i++) {
if (intervals < intervals){
intervals = Math.min(intervals, intervals);
count++;
}
}
return count;
}
} 763.划分字母区间
在遍历的过程中相当于是要找每一个字母的边界，假如找到之前遍历过的全部字母的最远边界，说明这个边界就是分割点了。此时前面出现过全部字母，最远也就到这个边界了。
可以分为如下两步：
[*]统计每一个字符最后出现的位置（很妙，这个记录法，详见代码部门）
[*]重新遍历字符，并更新字符的最远出现下标，假如找到字符最远出现位置下标和当前下标相等了，则找到了分割点
https://i-blog.csdnimg.cn/direct/ea399e0847524d31a875a2fb0cc91d0c.png
代码部门留意看下面那个简洁部门，注释的部门for循环中有点麻烦。但是思路逻辑什么的都是一样的。
class Solution {
public List<Integer> partitionLabels(String s) {
// int[] str = new int;
// for (int i = 0; i < s.length(); i++) {
// str = i; // 记录每个字符出现的最后一次的index
// }
// List<Integer> result = new LinkedList<>();
// for (int i = 0, start = 0, end = str; i < s.length(); i++) {
// if (i == end){
// result.add(end-start+1);
// if (i == s.length()-1){
// break;
// }
// end = str;
// start = i+1;
// }else {
// end = Math.max(end,str);
// }
// }
// return result;
//简洁版本
int[] str = new int;
for (int i = 0; i < s.length(); i++) {
str = i; // 记录每个字符出现的最后一次的index
}
List<Integer> result = new LinkedList<>();
for (int i = 0, start = -1, end = 0; i < s.length(); i++) {
end = Math.max(end,str);
if (i == end){
result.add(end-start);
start = i;
}
}
return result;
}
} 第三十天的总算是结束了，直冲Day31！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]