1. 贪心算法实战三道经典问题的解法与思考最近在刷代码随想录的贪心算法部分遇到了三道非常有意思的题目452用最少数量的箭引爆气球、435无重叠区间和763划分字母区间。这三道题看似不同实则都体现了贪心算法的核心思想——局部最优解能导向全局最优解。作为算法学习路上的必经关卡贪心算法常常让人又爱又恨。今天我就来详细拆解这三道题的解题思路分享一些我在刷题过程中总结的实用技巧。贪心算法在解决某些特定类型问题时表现出色特别是那些具有贪心选择性质的问题。简单来说就是每一步都做出当前看起来最优的选择希望这样能导致全局最优解。这三道区间相关的问题正是贪心算法的典型应用场景。接下来我会逐一分析每道题目的解法并解释为什么贪心策略在这里有效。2. 452. 用最少数量的箭引爆气球2.1 问题描述与直观理解这道题描述的是在二维平面上有许多气球每个气球的直径范围用区间表示例如[1,6]表示直径从1到6。我们需要用最少数量的垂直箭矢射穿所有气球箭矢的x坐标只要落在气球直径范围内就能射穿该气球。举个例子 输入[[10,16],[2,8],[1,6],[7,12]] 输出2 解释可以在x6处射爆[2,8]和[1,6]在x11处射爆[10,16]和[7,12]2.2 贪心策略的选择解决这个问题的关键在于认识到如果我们能找到一个点它能射穿尽可能多的重叠气球那么就能最小化箭的数量。这正符合贪心算法的思想——每一步都选择能射穿最多气球的点。具体实现步骤将所有区间按照结束点进行排序初始化箭的位置为第一个区间的结束点遍历后续区间如果当前区间的开始点小于等于箭的位置说明可以被同一支箭射穿否则需要增加一支新箭并更新箭的位置为当前区间的结束点def findMinArrowShots(points): if not points: return 0 points.sort(keylambda x: x[1]) arrows 1 first_end points[0][1] for start, end in points: if start first_end: arrows 1 first_end end return arrows2.3 为什么按结束点排序这里有个关键点为什么要按结束点而不是开始点排序试想如果我们按开始点排序可能会遇到这样的情况一个很长的区间覆盖了很多短区间但实际上我们可能希望优先处理结束早的区间这样能更早地释放箭的位置给后续区间使用。提示在区间问题上排序方式的选择往往决定了贪心策略能否成功。对于这类覆盖问题通常按结束点排序更有效。3. 435. 无重叠区间3.1 问题描述与转化这道题要求我们从一组区间中移除最少数量的区间使得剩下的区间互不重叠。这实际上可以转化为如何选择最多的不重叠区间。例如 输入[[1,2],[2,3],[3,4],[1,3]] 输出1 解释移除[1,3]后剩下的区间都不重叠3.2 贪心解法思路这个问题与上一题有异曲同工之妙。我们同样可以按照结束点排序然后尽可能选择结束早的区间这样能给后续区间留下更多空间。具体步骤按结束点排序所有区间初始化计数为1记录当前选中区间的结束点遍历区间如果当前区间的开始点不小于前一个选中区间的结束点则选择该区间def eraseOverlapIntervals(intervals): if not intervals: return 0 intervals.sort(keylambda x: x[1]) count 1 end intervals[0][1] for i in range(1, len(intervals)): if intervals[i][0] end: count 1 end intervals[i][1] return len(intervals) - count3.3 实际应用场景这类问题在实际中有很多应用比如课程安排如何在有限时间内安排最多课程会议室预定如何安排最多会议不冲突任务调度如何选择最多互不冲突的任务理解这个算法后你会发现它其实是一种非常实用的时间管理策略——总是优先处理最早结束的任务/事件。4. 763. 划分字母区间4.1 问题描述与特点这道题要求我们将字符串划分为尽可能多的片段使得每个字母最多出现在一个片段中并返回这些片段的长度列表。例如 输入S ababcbacadefegdehijhklij 输出[9,7,8] 解释 划分结果是 ababcbaca, defegde, hijhklij4.2 贪心策略的应用这个问题看似与前两个不同但实际上也可以转化为区间问题。我们需要首先记录每个字母最后出现的位置然后遍历字符串维护当前片段的开始和结束位置当遍历到当前片段的结束位置时表示可以划分一个片段def partitionLabels(S): last {c: i for i, c in enumerate(S)} start end 0 result [] for i, c in enumerate(S): end max(end, last[c]) if i end: result.append(end - start 1) start end 1 return result4.3 为什么这样有效这个解法巧妙地利用了贪心思想对于当前字符我们必须把它和它最后一次出现的位置包含在同一个片段中。因此在遍历过程中我们不断扩展当前片段的边界直到达到所有字符的最后出现位置。注意这类字符串划分问题常常可以转化为区间覆盖问题这是算法问题中一个重要的模式识别技巧。5. 贪心算法解题的通用思路通过这三道题我们可以总结出贪心算法解决区间问题的一些通用模式排序是关键大多数贪心算法问题都需要先对数据进行某种排序。在区间问题中通常按开始点或结束点排序。选择标准明确贪心算法每一步的选择标准必须明确。在上述问题中我们或者选择结束最早的区间或者选择必须包含某些元素的最小范围。证明贪心选择性质虽然在实际解题时我们可能不会严格证明但理解为什么贪心选择能得到全局最优很重要。通常这需要证明贪心选择存在于某个最优解中做出贪心选择后子问题与原问题具有相同结构处理边界条件特别是对于空输入、单个元素输入等情况要特别注意。6. 常见错误与调试技巧在解决这类问题时我遇到过不少坑这里分享几个常见错误和解决方法排序方式选择错误症状得到的结果不是最优解解决尝试不同的排序方式开始点、结束点、长度等理解每种排序对结果的影响边界条件处理不当症状对于空输入或单元素输入返回错误结果解决在代码开头显式处理这些特殊情况更新条件错误症状计数或指针更新时机不正确解决在纸上画出几个测试用例一步步模拟算法执行过程区间重叠判断错误症状错误判断两个区间是否重叠解决记住基本判断两个区间[a,b]和[c,d]重叠的条件是bc且da7. 复杂度分析与优化让我们分析一下这三个算法的复杂度用最少数量的箭引爆气球时间复杂度O(nlogn)来自排序遍历是O(n)空间复杂度O(1)或O(n)取决于排序实现无重叠区间时间复杂度O(nlogn)来自排序遍历是O(n)空间复杂度O(1)或O(n)划分字母区间时间复杂度O(n)构建last字典是O(n)遍历也是O(n)空间复杂度O(1)因为字母数量是固定的假设英文字母优化方向对于Python使用内置的sort()方法已经足够高效可以尝试在某些情况下提前终止循环对于划分字母区间问题如果字符串很长但字母种类很少可以考虑更紧凑的存储方式8. 测试用例设计为了验证代码的正确性我通常会设计以下几类测试用例常规情况多个重叠区间多个不重叠区间混合情况边界情况空输入单个区间所有区间完全相同超大输入测试性能特殊模式完全包含的区间如[1,10]和[2,3]刚好接触但不重叠的区间如[1,2]和[2,3]例如对于引爆气球问题测试用例示例 assert findMinArrowShots([[10,16],[2,8],[1,6],[7,12]]) 2 assert findMinArrowShots([[1,2],[3,4],[5,6],[7,8]]) 4 assert findMinArrowShots([[1,2],[2,3],[3,4],[4,5]]) 2 assert findMinArrowShots([]) 0 assert findMinArrowShots([[1,2]]) 19. 贪心算法的适用场景通过这三道题我们可以总结出贪心算法适用的一些场景区间调度问题如会议安排、课程选择等覆盖问题如选择最少的点覆盖所有区间划分问题如将元素划分为满足特定条件的子集最短路径问题如Dijkstra算法压缩编码问题如Huffman编码贪心算法在这些场景下有效通常是因为问题具有以下性质之一贪心选择性质局部最优解能导向全局最优解最优子结构问题的最优解包含子问题的最优解10. 从这三道题中学到的经验区间问题的处理模式排序是第一步通常按开始或结束点排序维护关键指针或变量如当前结束点线性扫描并做出贪心选择贪心选择的直觉培养对于引爆气球问题选择最早结束的区间可以最大化后续选择空间对于无重叠区间选择最早结束的区间可以保留最多空间给其他区间对于划分字母区间必须包含所有相同字符的最后出现位置代码实现的细节Python中使用lambda作为排序键注意区间是开区间还是闭区间边界条件的处理要小心调试技巧画图帮助理解区间关系使用小例子手动模拟算法执行添加打印语句跟踪关键变量变化贪心算法看似简单但要真正掌握需要大量的练习和思考。这三道区间问题提供了很好的学习素材它们展示了贪心算法在不同场景下的灵活应用。记住贪心算法的核心在于每步都做出局部最优选择但要验证这个选择是否能导向全局最优解。在实际编程面试中这类问题非常常见掌握它们的解题模式能大大提高解题效率。
1. 贪心算法实战三道经典问题的解法与思考最近在刷代码随想录的贪心算法部分遇到了三道非常有意思的题目452用最少数量的箭引爆气球、435无重叠区间和763划分字母区间。这三道题看似不同实则都体现了贪心算法的核心思想——局部最优解能导向全局最优解。作为算法学习路上的必经关卡贪心算法常常让人又爱又恨。今天我就来详细拆解这三道题的解题思路分享一些我在刷题过程中总结的实用技巧。贪心算法在解决某些特定类型问题时表现出色特别是那些具有贪心选择性质的问题。简单来说就是每一步都做出当前看起来最优的选择希望这样能导致全局最优解。这三道区间相关的问题正是贪心算法的典型应用场景。接下来我会逐一分析每道题目的解法并解释为什么贪心策略在这里有效。2. 452. 用最少数量的箭引爆气球2.1 问题描述与直观理解这道题描述的是在二维平面上有许多气球每个气球的直径范围用区间表示例如[1,6]表示直径从1到6。我们需要用最少数量的垂直箭矢射穿所有气球箭矢的x坐标只要落在气球直径范围内就能射穿该气球。举个例子 输入[[10,16],[2,8],[1,6],[7,12]] 输出2 解释可以在x6处射爆[2,8]和[1,6]在x11处射爆[10,16]和[7,12]2.2 贪心策略的选择解决这个问题的关键在于认识到如果我们能找到一个点它能射穿尽可能多的重叠气球那么就能最小化箭的数量。这正符合贪心算法的思想——每一步都选择能射穿最多气球的点。具体实现步骤将所有区间按照结束点进行排序初始化箭的位置为第一个区间的结束点遍历后续区间如果当前区间的开始点小于等于箭的位置说明可以被同一支箭射穿否则需要增加一支新箭并更新箭的位置为当前区间的结束点def findMinArrowShots(points): if not points: return 0 points.sort(keylambda x: x[1]) arrows 1 first_end points[0][1] for start, end in points: if start first_end: arrows 1 first_end end return arrows2.3 为什么按结束点排序这里有个关键点为什么要按结束点而不是开始点排序试想如果我们按开始点排序可能会遇到这样的情况一个很长的区间覆盖了很多短区间但实际上我们可能希望优先处理结束早的区间这样能更早地释放箭的位置给后续区间使用。提示在区间问题上排序方式的选择往往决定了贪心策略能否成功。对于这类覆盖问题通常按结束点排序更有效。3. 435. 无重叠区间3.1 问题描述与转化这道题要求我们从一组区间中移除最少数量的区间使得剩下的区间互不重叠。这实际上可以转化为如何选择最多的不重叠区间。例如 输入[[1,2],[2,3],[3,4],[1,3]] 输出1 解释移除[1,3]后剩下的区间都不重叠3.2 贪心解法思路这个问题与上一题有异曲同工之妙。我们同样可以按照结束点排序然后尽可能选择结束早的区间这样能给后续区间留下更多空间。具体步骤按结束点排序所有区间初始化计数为1记录当前选中区间的结束点遍历区间如果当前区间的开始点不小于前一个选中区间的结束点则选择该区间def eraseOverlapIntervals(intervals): if not intervals: return 0 intervals.sort(keylambda x: x[1]) count 1 end intervals[0][1] for i in range(1, len(intervals)): if intervals[i][0] end: count 1 end intervals[i][1] return len(intervals) - count3.3 实际应用场景这类问题在实际中有很多应用比如课程安排如何在有限时间内安排最多课程会议室预定如何安排最多会议不冲突任务调度如何选择最多互不冲突的任务理解这个算法后你会发现它其实是一种非常实用的时间管理策略——总是优先处理最早结束的任务/事件。4. 763. 划分字母区间4.1 问题描述与特点这道题要求我们将字符串划分为尽可能多的片段使得每个字母最多出现在一个片段中并返回这些片段的长度列表。例如 输入S ababcbacadefegdehijhklij 输出[9,7,8] 解释 划分结果是 ababcbaca, defegde, hijhklij4.2 贪心策略的应用这个问题看似与前两个不同但实际上也可以转化为区间问题。我们需要首先记录每个字母最后出现的位置然后遍历字符串维护当前片段的开始和结束位置当遍历到当前片段的结束位置时表示可以划分一个片段def partitionLabels(S): last {c: i for i, c in enumerate(S)} start end 0 result [] for i, c in enumerate(S): end max(end, last[c]) if i end: result.append(end - start 1) start end 1 return result4.3 为什么这样有效这个解法巧妙地利用了贪心思想对于当前字符我们必须把它和它最后一次出现的位置包含在同一个片段中。因此在遍历过程中我们不断扩展当前片段的边界直到达到所有字符的最后出现位置。注意这类字符串划分问题常常可以转化为区间覆盖问题这是算法问题中一个重要的模式识别技巧。5. 贪心算法解题的通用思路通过这三道题我们可以总结出贪心算法解决区间问题的一些通用模式排序是关键大多数贪心算法问题都需要先对数据进行某种排序。在区间问题中通常按开始点或结束点排序。选择标准明确贪心算法每一步的选择标准必须明确。在上述问题中我们或者选择结束最早的区间或者选择必须包含某些元素的最小范围。证明贪心选择性质虽然在实际解题时我们可能不会严格证明但理解为什么贪心选择能得到全局最优很重要。通常这需要证明贪心选择存在于某个最优解中做出贪心选择后子问题与原问题具有相同结构处理边界条件特别是对于空输入、单个元素输入等情况要特别注意。6. 常见错误与调试技巧在解决这类问题时我遇到过不少坑这里分享几个常见错误和解决方法排序方式选择错误症状得到的结果不是最优解解决尝试不同的排序方式开始点、结束点、长度等理解每种排序对结果的影响边界条件处理不当症状对于空输入或单元素输入返回错误结果解决在代码开头显式处理这些特殊情况更新条件错误症状计数或指针更新时机不正确解决在纸上画出几个测试用例一步步模拟算法执行过程区间重叠判断错误症状错误判断两个区间是否重叠解决记住基本判断两个区间[a,b]和[c,d]重叠的条件是bc且da7. 复杂度分析与优化让我们分析一下这三个算法的复杂度用最少数量的箭引爆气球时间复杂度O(nlogn)来自排序遍历是O(n)空间复杂度O(1)或O(n)取决于排序实现无重叠区间时间复杂度O(nlogn)来自排序遍历是O(n)空间复杂度O(1)或O(n)划分字母区间时间复杂度O(n)构建last字典是O(n)遍历也是O(n)空间复杂度O(1)因为字母数量是固定的假设英文字母优化方向对于Python使用内置的sort()方法已经足够高效可以尝试在某些情况下提前终止循环对于划分字母区间问题如果字符串很长但字母种类很少可以考虑更紧凑的存储方式8. 测试用例设计为了验证代码的正确性我通常会设计以下几类测试用例常规情况多个重叠区间多个不重叠区间混合情况边界情况空输入单个区间所有区间完全相同超大输入测试性能特殊模式完全包含的区间如[1,10]和[2,3]刚好接触但不重叠的区间如[1,2]和[2,3]例如对于引爆气球问题测试用例示例 assert findMinArrowShots([[10,16],[2,8],[1,6],[7,12]]) 2 assert findMinArrowShots([[1,2],[3,4],[5,6],[7,8]]) 4 assert findMinArrowShots([[1,2],[2,3],[3,4],[4,5]]) 2 assert findMinArrowShots([]) 0 assert findMinArrowShots([[1,2]]) 19. 贪心算法的适用场景通过这三道题我们可以总结出贪心算法适用的一些场景区间调度问题如会议安排、课程选择等覆盖问题如选择最少的点覆盖所有区间划分问题如将元素划分为满足特定条件的子集最短路径问题如Dijkstra算法压缩编码问题如Huffman编码贪心算法在这些场景下有效通常是因为问题具有以下性质之一贪心选择性质局部最优解能导向全局最优解最优子结构问题的最优解包含子问题的最优解10. 从这三道题中学到的经验区间问题的处理模式排序是第一步通常按开始或结束点排序维护关键指针或变量如当前结束点线性扫描并做出贪心选择贪心选择的直觉培养对于引爆气球问题选择最早结束的区间可以最大化后续选择空间对于无重叠区间选择最早结束的区间可以保留最多空间给其他区间对于划分字母区间必须包含所有相同字符的最后出现位置代码实现的细节Python中使用lambda作为排序键注意区间是开区间还是闭区间边界条件的处理要小心调试技巧画图帮助理解区间关系使用小例子手动模拟算法执行添加打印语句跟踪关键变量变化贪心算法看似简单但要真正掌握需要大量的练习和思考。这三道区间问题提供了很好的学习素材它们展示了贪心算法在不同场景下的灵活应用。记住贪心算法的核心在于每步都做出局部最优选择但要验证这个选择是否能导向全局最优解。在实际编程面试中这类问题非常常见掌握它们的解题模式能大大提高解题效率。
