代码随想录算法训练营第三十天

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

题目链接 用最少数量的箭引爆气球

题解

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
        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;
    }
}

解题思路

这段代码实现了一个求解最少弓箭数量的算法，用于解决区间重叠问题。让我来解释一下它的工作原理：

这个问题可以理解为：在二维平面上有许多气球，每个气球用一个区间 [start, end] 表示其水平直径范围。一支弓箭垂直射出，可以刺破所有区间包含该点的气球。求最少需要多少支弓箭才能刺破所有气球。

代码的核心思路是贪心算法：

1. 首先对所有气球区间按照起始点（start）进行排序
2. 初始化弓箭数量为 1（至少需要一支弓箭）
3. 遍历所有气球区间：
   • 如果当前气球的起始点大于前一个气球的结束点，说明两个气球不重叠，需要额外一支弓箭
   • 否则，说明两个气球可以被同一支弓箭刺破，更新当前气球的结束点为两个气球结束点的最小值（这是为了确保后续判断的准确性）

这种方法的时间复杂度是 O (n log n)，主要来自排序操作，空间复杂度是 O (1)（不考虑排序所需的空间）。

LeetCode.435 无重叠区间

题目链接 无重叠区间

题解

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

解题思路

这段 这段代码实现了一个求解 "删除重叠区间" 问题的算法。让我为你解释它的工作原理：

这个问题的核心是：给定一系列区间，找出需要删除的最少区间数量，使得剩余的区间互不重叠。

代码采用了贪心算法的思想，具体实现步骤如下：

1. 首先对所有区间按照起始点（start）进行排序

2. 初始化需要删除的区间数量 res 为 0

3. 遍历所有区间：

   • 如果当前区间的起始点小于前一个区间的结束点，说明两个区间重叠
     • 需要删除一个区间，所以 res 加 1
     • 保留结束点较小的那个区间（这是贪心选择，为了给后续区间留出更多空间）
   • 如果不重叠，则继续检查下一个区间

4. 最后返回需要删除的区间总数 res

这种方法的时间复杂度是 O (n log n)，主要来自排序操作，空间复杂度是 O (1)（不考虑排序所需的空间）。

LeetCode.763 划分字母区间

题目链接 划分字母区间

题解

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList<>();
        Map<Character,Integer> map = new HashMap<>();
        for(int i = 0;i<s.length();i++){
            map.put(s.charAt(i),i);
        }
        int idx = 0;
        int last = -1;
        for(int i = 0;i<s.length();i++){
            char c = s.charAt(i);
            idx = Math.max(idx,map.get(c));
            if(i == idx) {
                res.add(idx - last);
                last = i;
            }
            
        }
        return res;
    }
}

解题思路

这段代码实现了字符串分区的功能，解决的是 "划分字母区间" 的问题。让我为你详细解释它的工作原理：

问题描述：将字符串划分为尽可能多的片段，使得每个字母只出现在一个片段中。返回每个片段的长度。

代码采用了贪心算法的思想，具体实现步骤如下：

1. 首先创建一个哈希表（map）存储每个字符最后出现的位置

   • 遍历字符串，记录每个字符最后一次出现的索引位置

2. 然后再次遍历字符串，确定每个分区的边界：

   • idx 表示当前分区的最远边界
   • last 表示上一个分区的结束位置（初始为 - 1）
   • 对于每个字符，更新当前分区的最远边界为该字符最后出现的位置
   • 当遍历到的索引 i 等于当前分区的最远边界 idx 时，说明找到了一个完整的分区
     • 计算分区长度（idx - last）并加入结果列表
     • 更新 last 为当前分区的结束位置 i

这种方法的时间复杂度是 O (n)（n 为字符串长度），需要遍历字符串两次；空间复杂度是 O (1)，因为最多只会存储 26 个字母的位置信息。

例如，对于字符串 "ababcbacadefegdehijhklij"，代码会将其划分为 ["ababcbaca", "defegde", "hijhklij"] 三个区间，返回的长度列表为 [9,7,8]。

这个算法的关键在于：通过记录每个字符的最后出现位置，确保每个分区包含了该区间内所有字符的所有出现，从而实现了每个字母只出现在一个片段中的要求。