452. 用最少数量的箭引爆气球
题目链接:452. 用最少数量的箭引爆气球
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰452. 用最少数量的箭引爆气球
日期:2024-10-05
想法:对气球起点排序,没有重叠的箭头+1,有重叠得话将右边置为最小的右边。
Java代码如下:
class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));int res = 1;for(int i = 1; i < points.length; i++) {if(points[i][0] > points[i - 1][1]) {res++;}else {points[i][1] = Math.min(points[i - 1][1], points[i][1]);}}return res;}
}
435. 无重叠区间
题目链接:435. 无重叠区间
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰无重叠区间
日期:2024-10-05
想法:与气球很相似,选右边最短的就相当于删除了一次。
Java代码如下:
class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));int res = 0;for(int i = 1; i < intervals.length; i++) {if(intervals[i][0] < intervals[i - 1][1]) {intervals[i][1] = Math.min(intervals[i - 1][1], intervals[i][1]);res++;}}return res;}
}
763.划分字母区间
题目链接:763.划分字母区间
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰划分字母区间
日期:2024-10-05
Java代码如下:
class Solution {public List<Integer> partitionLabels(String S) {List<Integer> list = new LinkedList<>();int[] hash = new int[26];char[] chars = S.toCharArray();for (int i = 0; i < chars.length; i++) {hash[chars[i] - 'a'] = i;}int left = 0;int right = 0;for (int i = 0; i < chars.length; i++) {right = Math.max(right, hash[chars[i] - 'a']);if (i == right) {list.add(i - left + 1);left = i + 1;}}return list;}
}