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

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[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 partitionLabels(String s) { List res = new ArrayList(); Map 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]。

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