第八章 贪心算法 part04
今天的三道题目，都算是 重叠区间 问题，大家可以好好感受一下。 都属于那种看起来好复杂，但一看贪心解法，惊呼：这么巧妙！
这种题还是属于那种，做过了也就会了，没做过就很难想出来。
不过大家把如下三题做了之后， 重叠区间 基本上差不多了
452. 用最少数量的箭引爆气球
class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, (a, b) -> {return a[0] - b[0];});
int result = 1;
for(int i = 1; i < points.length; i ++){
if(points[i][0] > points[i - 1][1]){
result ++;
}else{
points[i][1] = Math.min(points[i][1], points[i-1][1]);
}
}
return result;
}
}
错误：
输入
points =
[[-2147483646,-2147483645],[2147483646,2147483647]]
输出
1
预期结果
2
class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
int result = 1;
for(int i = 1; i < points.length; i ++){
if(points[i][0] > points[i - 1][1]){
result ++;
}else{
points[i][1] = Math.min(points[i][1], points[i-1][1]);
}
}
return result;
}
}
435. 无重叠区间
https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html
class Solution {
public int eraseOverlapIntervals(int[][] points) {
Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
int result = 0;
for(int i = 1; i < points.length; i ++){
if(points[i][0] < points[i - 1][1]){
result ++;
points[i][1] = Math.min(points[i][1], points[i-1][1]);
}
}
return result;
}
}
763.划分字母区间
https://programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html
class Solution {
public List<Integer> partitionLabels(String s) {
int[] hash = new int[26];
for(int i = 0; i < s.length(); i ++){
hash[s.charAt(i) - 'a'] = i;
}
List<Integer> result = new LinkedList<>();
int left = 0;
int right = 0;
for(int i = 0; i < s.length(); i ++){
if(hash[s.charAt(i) - 'a'] == i){
right = i;
result.add(right - left + 1);
}
left = right;
}
return result;
}
}
s =
"ababcbacadefegdehijhklij"
输出
[6,3,2,4,3,2,2,5,2,2,2,2]
预期结果
[9,7,8]
class Solution {
public List<Integer> partitionLabels(String s) {
int[] hash = new int[26];
for(int i = 0; i < s.length(); i ++){
hash[s.charAt(i) - 'a'] = i;
}
List<Integer> result = new LinkedList<>();
int left = 0;
int right = 0;
for(int i = 0; i < s.length(); i ++){
right = Math.max(right, hash[s.charAt(i) - 'a']);
if(right == i){
result.add(right - left + 1);
}
left = right;
}
return result;
}
}
s =
"ababcbacadefegdehijhklij"
输出
[1,1,1]
预期结果
[9,7,8]
class Solution {
public List<Integer> partitionLabels(String s) {
int[] hash = new int[26];
for(int i = 0; i < s.length(); i ++){
hash[s.charAt(i) - 'a'] = i;
}
List<Integer> result = new LinkedList<>();
int left = 0;
int right = 0;
for(int i = 0; i < s.length(); i ++){
right = Math.max(right, hash[s.charAt(i) - 'a']);
if(right == i){
result.add(right - left + 1);
left = right + 1;//位置还有加一
}
}
return result;
}
}
