算法训练（leetcode）二刷第二十六天 | *452. 用最少数量的箭引爆气球、435. 无重叠区间、*763. 划分字母区间

*452. 用最少数量的箭引爆气球

leetcode题目地址

先对气球的坐标按照X_start进行升序排序，只要两个气球之间挨着就可以一箭射穿，因此排序后查看后一个气球的起始坐标是否与前一个气球的结束坐标挨着（挨着：后一个起始坐标<=前一个结束坐标）。

时间复杂度： $O(nlogn)$
空间复杂度： $O(1)$

// java
class Solution {
    public int findMinArrowShots(int[][] points) {
        // 按照起始坐标从小到大排序 
        // 使用Integer内置比较方法，不会溢出
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
        int cnt = 1;
        for(int i=1; i<points.length; i++){
            if(points[i][0] > points[i-1][1]){
                  cnt++;
            }else{
                points[i][1] = Math.min(points[i][1], points[i-1][1]); 
            }
            // System.out.println(points[i][0] + " " + points[i][1]);
        }
        return cnt;
    }
}

435. 无重叠区间

leetcode题目地址

和上题思路类似。本题是找到有重叠的区间，然后删除覆盖范围较大的那一个。先对区间进行排序，按照区间起始位置升序排序，若起始位置相同，则按照结束位置升序排序。

然后遍历数组，若后一个区间的起始位置小于前一个区间的结束位置（等于不算重叠），则两区间有重叠，删除后面的区间。这里的删除不是物理删除，是逻辑删除，更新后一个区间的结束区间即可，后一个区间的结束位置等于前一个区间的结束位置和后一个区间结束位置较小的那个。

时间复杂度： $O(nlogn)$
空间复杂度： $O(1)$

// java
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if(a[0] == b[0]){
                return Integer.compare(a[1], b[1]);
            }
            return Integer.compare(a[0], b[0]);
        });
        int cnt = 0;
        for(int i=1; i<intervals.length; i++){
            // 重叠
            if(intervals[i][0] < intervals[i-1][1]){
                cnt++;
                intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);
            }
        }
        return cnt;
    }
}

*763. 划分字母区间

leetcode题目地址

笨拙版

先统计字符串中每个字母的出现次数。
记录目前子串中出现的字母，若子串中的字母均已访问过则切分为一个子串记录长度。

使用map记录子串中的字母以及对应字母的剩余个数，当字母剩余0个时即当前字母访问结束从map中移除。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java
class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] chars = new int[26];
        for(int i=0; i<s.length(); i++){
            chars[s.charAt(i) - 'a']++;
        }
        List<Integer> result = new ArrayList<>();
        Map<Character, Integer> hash = new HashMap<>();
        int start = 0;
        
        for(int i=0; i<s.length(); i++){
            chars[s.charAt(i) - 'a']--;
            if(hash.containsKey(s.charAt(i))) hash.put(s.charAt(i), hash.get(s.charAt(i))-1);
            else hash.put(s.charAt(i), chars[s.charAt(i) - 'a']);
            if(hash.get(s.charAt(i)) == 0) hash.remove(s.charAt(i));
            
            if(hash.isEmpty()){
                result.add(i-start+1);
                start = i+1;
            }
        }
        return result;
        
    }
}

进阶版

先统计每个字符的最后出现的位置，当访问字符串时，若已到达子串中所有字符的最后位置，则记录当前子串长度。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

// java
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 ArrayList<>();
        
        int start = 0;
        int end = 0;
        for(int i=0; i<s.length(); i++){
            end = Math.max(end, hash[s.charAt(i) - 'a']);
            if(i == end){
                // 到达当前子串最右端
                result.add(end-start+1);
                start = i+1;
            }
        }
        return result;
        
    }
}