第三十天|贪婪算法| 452. 用最少数量的箭引爆气球，435. 无重叠区间 ，763. ...

目录
452. 用最少数量的箭引爆气球
435. 无重叠区间
763.划分字母区间

---

本日的题目都算是 重叠区间 题目。
452. 用最少数量的箭引爆气球

为了让气球尽大概的重叠，必要对数组举行排序。
假如气球重叠了，重叠气球中右边边界的最小值 之前的区间肯定必要一个弓箭。

1.     class Solution {
2.         public int findMinArrowShots(int[][] points) {
3. //            Arrays.sort(points, (a, b) -> {
4. //                if (a[0] == b[0]) {
5. //                    return Integer.compare(a[1], b[1]);
6. //                }
7. //                return Integer.compare(a[0], b[0]);
8. //            });
9.             Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
10.             int count = 1; // points 不为空至少需要一支箭
11.             for (int i = 1; i < points.length; i++) {
12.                 if (points[i][0] > points[i - 1][1]) {
13.                     count++;
14.                 } else {
15.                     points[i][1] = Math.min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界
16.                 }
17.             }
18.             return count;
19.         }
20.     }

复制代码

• 时间复杂度：O(nlog n)，排序必要 O(NlogN) 的复杂度
  
• 空间复杂度：O( log n)，java所利用的内置函数用的是快速排序必要 logN 的空间
  

留意，排序这块必要用 Integer.compare(a[0], b[0])
由于一开始我用的是：

1. if (a[0] == b[0]) {
2.     return a[1] - b[1];
3. }
4. return a[0] - b[0];

复制代码

当数组包含极大或极小的整数（如 Integer.MIN_VALUE 和 Integer.MAX_VALUE）时，直接利用减法盘算差值大概导致 整数溢出，则会产生溢出错误。
为了制止溢出，可以利用 Integer.compare 方法代替减法，由于它可以安全地比较两个整数而不会产生溢出。Integer.compare(a[0], b[0])：会返回一个负值、零或正值，分别表示 a[0] 小于、即是或大于 b[0]。
435. 无重叠区间

按左边排序，不管右边次序。相交的时候取最小的右边。
与452很类似，简朴。

1. class Solution {
2.     public int eraseOverlapIntervals(int[][] intervals) {
3.         if (intervals.length == 1) {
4.             return 0;
5.         }
6.         Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
7.         int count = 0;
8.         for (int i = 1; i < intervals.length; i++) {
9.             if (intervals[i][0] < intervals[i-1][1]){
10.                 intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);
11.                 count++;
12.             }
13.         }
14.         return count;
15.     }
16. }

复制代码

763.划分字母区间

在遍历的过程中相当于是要找每一个字母的边界，假如找到之前遍历过的全部字母的最远边界，说明这个边界就是分割点了。此时前面出现过全部字母，最远也就到这个边界了。
可以分为如下两步：

• 统计每一个字符最后出现的位置（很妙，这个记录法，详见代码部门）
  
• 重新遍历字符，并更新字符的最远出现下标，假如找到字符最远出现位置下标和当前下标相等了，则找到了分割点
  

代码部门留意看下面那个简洁部门，注释的部门for循环中有点麻烦。但是思路逻辑什么的都是一样的。

1.     class Solution {
2.         public List<Integer> partitionLabels(String s) {
3. //            int[] str = new int[26];
4. //            for (int i = 0; i < s.length(); i++) {
5. //                str[s.charAt(i) - 'a'] = i; // 记录每个字符出现的最后一次的index
6. //            }
7. //            List<Integer> result = new LinkedList<>();
8. //            for (int i = 0, start = 0, end = str[s.charAt(0)-'a']; i < s.length(); i++) {
9. //                if (i == end){
10. //                    result.add(end-start+1);
11. //                    if (i == s.length()-1){
12. //                        break;
13. //                    }
14. //                    end = str[s.charAt(i+1)-'a'];
15. //                    start = i+1;
16. //                }else {
17. //                    end = Math.max(end,str[s.charAt(i)-'a']);
18. //                }
19. //            }
20. //            return result;
21.             
22.             //简洁版本
23.             int[] str = new int[27];
24.             for (int i = 0; i < s.length(); i++) {
25.                 str[s.charAt(i) - 'a'] = i; // 记录每个字符出现的最后一次的index
26.             }
27.             List<Integer> result = new LinkedList<>();
28.             for (int i = 0, start = -1, end = 0; i < s.length(); i++) {
29.                 end = Math.max(end,str[s.charAt(i)-'a']);
30.                 if (i == end){
31.                     result.add(end-start);
32.                     start = i;
33.                 }
34.             }
35.             return result;
36.         }
37.     }

复制代码

第三十天的总算是结束了，直冲Day31！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。