452. 用最少数量的箭引爆气球
自己写没写出来，不过找到篇很好的题解，贪心想不到就是想不到，没办法。本以为自己的思路也是贪心，但就是做不出来。
class Solution {
public int findMinArrowShots(int[][] points) {
boolean[] visited = new boolean[points.length];
Arrays.sort(points, (a, b)-> Integer.compare(a[1], b[1]));
int res = 1;
int rightMax = points[0][1];
for(int i = 1; i < points.length; i++){
if(points[i][0] <= rightMax) continue;
res++;
rightMax = points[i][1];
}
return res;
}
}
435. 无重叠区间
做完上一道题再看这个就会容易许多。按照区间右端点升序排序，显然第一个区间一定是要保留的（对于右边界相等的情况，保留任意一个都可，因为结果都一样，这点可以看力扣官解贪心思路，官解这次讲的很清楚），因为没有比他更左边的区间。然后我们去找到第一个不和该区间重合的区间作为下一个可以保留的区间（由于数组按照右端点排序，一定能保证此时是最左的）。其实这种题还是画个图最直观，最好理解。
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b)->{
return Integer.compare(a[1], b[1]);
});
int res = 0;
int right = intervals[0][1];
for(int i = 1; i < intervals.length; i++){
if(intervals[i][0] < right) res++;
else right = intervals[i][1];
}
return res;
}
}
56. 合并区间
做划分字母区间之间先做了这道题，因为我的划分字母区间用了这道题的思路。但这个也是看了题解才做出来。我做题总是跳脱不出之前题的套路，比如前面两道题都是用区间的右边界进行排序，这道题我也想当然的这么去做，结果就是绕死也绕不出来。但如果使用左边界排序，思路就清楚许多。
贪心贪在哪里？由于区间集合已经按照左边界进行升序排序，那么在遍历该集合时，若当前节点的左边界小于等于上一个节点的右边界，说明区间重合，因此就使用当前区间和上一个区间进行合并。当找到了第一个没有重合的集合时，说明前面的部分已经合并完成，继续迭代后面的部分即可。
class Solution {
public int[][] merge(int[][] intervals) {
if(intervals.length == 1) return intervals;
Arrays.sort(intervals, (a, b)->Integer.compare(a[0], b[0]));
int[] pre = intervals[0];
List<int[]> listAns = new ArrayList();
for(int i = 1; i < intervals.length;i ++){
if(intervals[i][0] <= pre[1]) {
pre[1] = Math.max(pre[1], intervals[i][1]);
}
else {
listAns.add(pre);
pre = intervals[i];
}
if(i==intervals.length-1) listAns.add(pre);
}
return listAns.toArray(new int[listAns.size()][]);
}
}
763. 划分字母区间
我的思路是与上一题很相似的，比起官解来还是复杂了一些。
首先遍历字符串，得到每个字母出现的第一个和最后一个位置，也就是得到了一组区间的集合。显然这些集合间可能有重合，因此，只需要将这些区间进行合并即可，合并的思路与56. 合并区间完全一致。按照左边界进行升序排序，遇到能合并的则合并即可。
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> ans = new ArrayList();
int[][] map = new int[26][2];
for(int[] t:map){
t[0] = -1;
t[1] = -1;
}
for(int i = 0; i < s.length(); i++){ //更新左右边界
if(map[s.charAt(i)-'a'][0] == -1) map[s.charAt(i)-'a'][0] = i;
map[s.charAt(i)-'a'][1] = i;
}
Arrays.sort(map, (x, y)->Integer.compare(x[0], y[0])); //按照区间左边界升序排序
int i = 0;
while(map[i][0] == -1) i++; //跳过不存在的字母
List<int[]> q = new ArrayList();
int[] pre = map[i]; //记录上一个区间
for(int j = i+1; j < map.length; j++){
if(map[j][0] <= pre[1]) { //如果上一个区间与当前区间有重合
pre[1] = Math.max(map[j][1], pre[1]); //扩展区间
}else{ //没有重合
q.add(pre); //后续都不会有重合的区间，存入结果中
pre = map[j];
}
}
q.add(pre);
q.forEach(a->ans.add(a[1]-a[0]+1));
return ans;
}
}
官解当然还是优雅啊，先遍历字符串，得到每个字母的末尾位置。使用end记录当前字串的区间的末尾，i==end说明已经找到了符合要求的区间。在遍历的的同时更新end。
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> ans = new ArrayList();
int[] map = new int[26];
for(int i = 0; i < s.length(); i++){
map[s.charAt(i)-'a'] = i;
}
int pre = -1, end = -1;
for(int i = 0; i < s.length(); i++){
end = Math.max(end, map[s.charAt(i)-'a']); //重点
if(i == end) {
ans.add(i-pre);
pre = i;
}
}
return ans;
}
}