452

题目：

在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

示例 1：

  • 输入：points = [[10,16],[2,8],[1,6],[7,12]]
  • 输出：2
  • 解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球

示例 2：

  • 输入：points = [[1,2],[3,4],[5,6],[7,8]]
  • 输出：4

示例 3：

  • 输入：points = [[1,2],[2,3],[3,4],[4,5]]
  • 输出：2

示例 4：

  • 输入：points = [[1,2]]
  • 输出：1

示例 5：

  • 输入：points = [[2,3],[2,3]]
  • 输出：1

提示

  • 1 <= points.length <= 105

  • points[i].length == 2

  • -2^31 <= xstart < xend <= 2^31 - 1

思路

根据题目中给出的条件开始坐标总是小于结束坐标。 ，首先可以按照开始坐标进行排序，以案例一为例：

points = [[1,2],[3,4],[5,6],[7,8]]

排序之后的结果就是

points = [[1,6],[2,8],[7,12],[10,16]]

这样， 就可以得到一组有序的序列， 通过判断另一组序列是否再要求的（xstart ≤ x ≤ xend）范围内即可得出， 这两组是否可以通过一根箭就引爆气球。

按照上述的思路 ，因为1 <= points.length <= 105， 所以至少需要消耗一根箭。所以说我们就可以通过判断当前气球直径范围的起始points[i][0]是否和 上一个气球直径范围的结束(points[i-1][1]) 是否重合 ? 如果重合， 那么就可以使用一根箭， 反之， 就需要使用俩

​ 以上就是我对这道题整体的一个判断， 当然，还有一点需要注意的就是。 如果重合了， 那么我们就需要更新最新的结尾范围xend。 拿案例一来说， [1,6] 和 [2,8] ，我们是只需要一根箭就可以完成引爆的， 但是后面的[7,12]呢，如果我们不去考虑结尾范围xend 那么points[i][1] == 8 ，但是[2,8] 是可以包括到7的 , 那么我们这里的x是取几呢？

​ 如果取7， 可是引爆[2,8] 和 [7,12], 那 [1,6]怎么办 ? 这不就和我们刚开始解题的初衷思考不符合了嘛。

​ 因此， 这里就需要实时更新xend ，来先考虑左边的，而不是顾此失彼。

1
points[i][1] = Math.min(points[i-1][1], points[i][1]);

如果重合， 那么就使用上述语句来更新最新的xend

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findMinArrowShots(int[][] points) {
        //先给所有的数组排序
        Arrays.sort(points, (a,b)-> Integer.compare(a[0],b[0]));
        //循环遍历， 如果出现两个边重合的直接 箭的数量不变
        int res = 1 ;  //数组不为0 ，就一定需要一只箭
        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

题目：

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1:

  • 输入: [ [1,2], [2,3], [3,4], [1,3] ]
  • 输出: 1
  • 解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

  • 输入: [ [1,2], [1,2], [1,2] ]
  • 输出: 2
  • 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

  • 输入: [ [1,2], [2,3] ]
  • 输出: 0
  • 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

提示:

  • 1 <= intervals.length <= 105
  • intervals[i].length == 2
  • -5 * 104 <= starti < endi <= 5 * 104

思路

本题和上面的 452 是有异曲同工之处的 可以认为区间的终点总是大于它的起点 都是终点大于起点。 这样我们考虑的时候就不需要考虑其他的了 ，现以一种方式来得到有序的序列。 然后再进行比较。

同时，本题对于相同的数， 不做重叠处理

按照这样的条件， 还是以案例一为例进行详解

输入： [ [1,2], [2,3], [3,4], [1,3] ]

先进行排序

[ [1,2], [1,3] , [2,3], [3,4] ]

按照上一道题的思路 ， 如果当前区间的起始interval[i][0] < 上一个区别的结尾intervals[i-1][1]。 那么就说明两个区间

  • 有重叠的部分， 此时就需要删除一个，因为结果只需要我们得到删除的个数 ，所以这里用count记录。 同时还需要对当前区间的结尾进行处理。我们是从左向右考虑的， 所以需要考虑前面的。所以这里intervals[i][1] == Math.min(intervals[i][1], intervals[i-1][1]) 。
  • 如果没有重叠的， 不需要删除， 所以直接continue即可

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        //先按照intervals[0] 来对二维数组排序
        Arrays.sort(intervals,(a,b)-> Integer.compare(a[0],b[0]));
        //得到的数组就是[0]有序， 但是[1]不确定的数据。我们只需要判断[1]是否有序即可
        int count = 0; //记录需要移除的个数
      //  int end = intervals[0][1];
        for(int i = 1 ; i< intervals.length; i++){
            //有重叠
            if(intervals[i][0] < intervals[i-1][1] ){
                //需要随时更新end 切割
                intervals[i][1] = Math.min(intervals[i-1][1], intervals[i][1]);
                count++;
            }else{
                //无重叠
                //intervals[i-1][1] = intervals[i][1];
                continue;
            }
        }
        return count;
    }
}

763

题目：

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

  • 输入：S = “ababcbacadefegdehijhklij”
  • 输出：[9,7,8] 解释： 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

提示：

  • S的长度在[1, 500]之间。
  • S只包含小写字母 ‘a’ 到 ‘z’ 。

思路

按照题目中同一字母最多出现在一个片段中 这个条件来划分单词的话， 首先我们需要统计每个单词在字符串中出现的最远距离， 我们从左向右遍历， 如果遍历一个单词它出现在字符串的最远距离 和 遍历的i也就是当前距离相等。 那么就说明后面他不会再出现了， 我们也就可以收集这个片段， 将其作为一个片段来。

​ 与此同时， 我们不仅需要考虑当前字母， 还需要考虑这个片段内的所有字母， 他们是否在这个片段之外都没有出现过， 如果是， 那么我们切割的这个片段就没问题。

​ 但是按照上述的思路， 得出来的一定会有问题，按照示例中的

S = “ababcbacadefegdehijhklij”

如果按照我们刚才的思路， 得到的结果就是

“ababcbaca”, “defegd”, “ehijhklij”。

很显然， 这是错的，因为第二个片段中的e在第三个片段中出现了， 第二个片段得到的并不是题目中要求的同一字母最多出现在一个片段中 。 所以说需要考虑这个片段内所有的字母。

​ **按照这个想法， 我们就需要一个变量来统计这个片段内的最远距离最大的那个字母。 他是否到达了它的最远距离.如果连这个字母都到达了最远距离， 那么这个片段也一定达到了题目的要求。 **

因此, 这里就需要的使用max函数， 来得到最远距离最大的那个字母。

1
2
3
int[] arr = new int[26];   // 存储26个字母对应的最后的位置
int right = 0; // 记录片段内出现的最远位置
right = Math.max(right , arr[s.charAt(i) - 'a'] );

然后 ，再记录片段的大小，将结果写入list集合即可

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] arr = new int[26];   // 存储26个字母对应的最后的位置
        for(int i= 0; i < s.length(); i++){
            arr[s.charAt(i) - 'a'] = i;
        }
        //得到的内容就是对应的字母最后出现的位置
        //分割
        int left = 0;
        int right = 0; // 记录片段内出现的最远位置
        List<Integer> list = new ArrayList<>();
        for(int i =0 ; i< s.length();i++){
            right = Math.max(right , arr[s.charAt(i) - 'a'] );
            if(i == right) {
                list.add(right - left + 1);
                left = i+1;   
            }
        }
        return list;
    }
}