代码随想录算法训练营第三十天-452用最少数量的箭引爆气球、435无重叠区间、763划分字母区间

前言
状态：可能因为熬夜，思绪都是飘的。都是看了解析写出来的。
更新

1	24-06-15 初始记录

初步题解

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

题目链接：(https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons)

没有思路。

435 无重叠区间

题目链接：(https://leetcode.cn/problems/non-overlapping-intervals)

还是没有思路。

763 划分字母区间

题目链接：(https://leetcode.cn/problems/partition-labels/description/)

直接看的解析。

看解析

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

解析：(https://programmercarl.com/0452.用最少数量的箭引爆气球.html)

/**  
 * 思路：看了一下题目就是要求重叠的区间  
 * 关键在于更新最小右边界  
 * @param points 坐标点  
 * @return 最小弓箭数  
 */  
public static int findMinArrowShots(int[][] points) {  
    Arrays.sort(points, Comparator.comparingInt(o -> o[0]));  
  
    if (points.length <= 1) {  
        return points.length;  
    }  
  
    int count = 1;  
    for (int i = 1; i < points.length; i++) {  
        if (points[i][0] > points[i - 1][1]) {  
            count++;  
        } else {  
            points[i][1] = Math.min(points[i][1], points[i - 1][1]);  
        }  
    }  
    return count;  
}

435 无重叠区间

解析：(https://programmercarl.com/0435.无重叠区间.html)

/**  
 * 思路：和上一题差不多，找重叠的，然后移除了  
 * @param intervals 区间的集合  
 * @return 结果  
 */  
public static int eraseOverlapIntervals(int[][] intervals) {  
    Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));  
  
    int count = 0;  
  
    if (intervals.length <= 1) {  
        return count;  
    }  
  
    for (int i = 1; i < intervals.length; i++) {  
        if (intervals[i][0] >= intervals[i - 1][1]){  
        } else {  
            count++;  
            intervals[i][1] = Math.min(intervals[i][1], intervals[i - 1][1]);  
        }  
    }  
  
    return count;  
}

763 划分字母区间

解析：(https://programmercarl.com/0763.划分字母区间.html)

/**  
 * 思路：  
 * 1. 找到每个字母的区间  
 * 2. 根据遍历中最远结束节点，更新切割位置  
 * @param s 字符串  
 * @return 结果  
 */  
public List<Integer> partitionLabels(String s) {  
    char[] chars = s.toCharArray();  
  
    // 记录每个字母最后出现的节点  
    int[] ints = new int[26];  
    Arrays.fill(ints, -1);  
    for (int i = 0; i < chars.length; i++) {  
        ints[chars[i] - 'a'] = i;  
    }  
  
    List<Integer> list = new ArrayList<>();  
  
    int idx = 0;  
    // 记录上一个切割的位置（用于计算存入list的长度）  
    int last = -1;  
    for (int i = 0; i < chars.length; i++) {  
        // 把节点更新为要结束的地方  
        idx = Math.max(idx, ints[chars[i] - 'a']);  
        // 直到可以结束  
        if (i == idx) {  
            list.add(i - last);  
            last = i;  
        }  
    }  
    return list;  
}