java-代码随想录第30天|452. 用最少数量的箭引爆气球、 435. 无重叠区间、 763.划分字母区间
·
452. 用最少数量的箭引爆气球
链接：452. 用最少数量的箭引爆气球 - 力扣（LeetCode）
题目：
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组
points，其中points[i] = [xstart, xend]表示水平直径在xstart和xend之间的气球。你不知道气球的确切 y 坐标。一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标
x处射出一支箭，若有一个气球的直径的开始和结束坐标为xstart，xend， 且满足xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。给你一个数组
points，返回引爆所有气球所必须射出的 最小 弓箭数 。
class Solution {
public int findMinArrowShots(int[][] points) {
// 根据气球直径的开始坐标从小到大排序
// 使用Integer内置比较方法，不会溢出
Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
int count = 1; // points 不为空至少需要一支箭
for (int i = 1; i < points.length; i++) {
//第一个气球的右边界 < 第二个气球的左边界
if (points[i][0] > points[i - 1][1]) { // 气球i和气球i-1不挨着，注意这里不是>=
count++; // 需要一支箭
} else { // 气球i和气球i-1挨着
points[i][1] = Math.min(points[i][1], points[i - 1][1]); // 更新重叠气球最小右边界
}
}
return count;
}
}435. 无重叠区间
题目：
给定一个区间的集合
intervals，其中intervals[i] = [starti, endi]。返回 需要移除区间的最小数量，使剩余区间互不重叠 。注意 只在一点上接触的区间是 不重叠的。例如
[1, 2]和[2, 3]是不重叠的。
class Solution {
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;
}
}763.划分字母区间
题目：
给你一个字符串
s。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串"ababcc"能够被分为["abab", "cc"]，但类似["aba", "bcc"]或["ab", "ab", "cc"]的划分是非法的。注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是
s。返回一个表示每个字符串片段的长度的列表。
class Solution {
public List<Integer> partitionLabels(String s) {
//创建list列表
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;
}
}更多推荐
7
0- 0
已为社区贡献9条内容
所有评论(0)