自学内容网 自学内容网
自学内容网 > 正文

day 30 第八章 贪心算法 part04

🕗 发布于 2024-12-01 06:16 算法  

第一题：452. 用最少数量的箭引爆气球

解题思路

本题要求根据给定的表示气球水平直径范围的二维数组 points，计算出引爆所有气球所需要射出的最小弓箭数，解题思路运用了贪心算法，核心思想是尽量让一支箭能穿过更多的气球，以下是详细说明：

  1. 整体思路：
    贪心算法在这里的体现是，我们希望每射出一支箭都能尽可能多地引爆气球，而不是随意射箭。通过对气球的直径范围按照起始位置进行排序，然后依次遍历气球，根据相邻气球的范围关系来判断是否可以用同一支箭引爆它们，不断合并可以用同一支箭引爆的气球范围，最终统计出最少需要射出的弓箭数量。

  2. 气球范围排序预处理：
    首先通过 Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0])) 对 points 数组按照每个气球直径范围的起始位置从小到大进行排序。这样做的好处是方便后续遍历气球时，能够按照顺序依次比较相邻气球的范围是否有重叠或者包含关系，便于做出贪心选择，确定哪些气球可以用同一支箭引爆。

  3. 遍历气球并处理重叠范围：
    初始化一个变量 count 为 1，它用于记录最终需要射出的弓箭数量（初始设为 1 是因为至少需要射出一支箭来引爆气球）。然后通过 for 循环从第二个气球开始遍历整个 points 数组（索引为 i，循环条件是 i < points.length），在循环中进行以下判断和操作：

    • 无重叠情况判断：
      当发现当前气球 points[i] 的起始位置 points[i][0] 大于前一个气球 points[i - 1][1]（也就是前一个气球的结束位置）时，说明这两个气球没有重叠部分，一支箭无法同时引爆它们，所以需要多射出一支箭，此时将 count 的值加 1。
    • 有重叠情况处理：
      如果当前气球的起始位置不大于前一个气球的结束位置，说明这两个气球有重叠或者包含关系，此时可以尝试用同一支箭来引爆它们，为了让这支箭能继续覆盖后面更多可能重叠的气球，我们选择更新当前气球的结束位置为两个气球结束位置中的较小值（通过 points[i][1] = Math.min(points[i][1], points[i - 1][1])），这样相当于缩小了当前气球的有效范围，使其更有可能与后面的气球继续保持能用同一支箭引爆的状态，然后继续循环去检查下一个气球与当前气球是否有重叠等情况。

  4. 计算并返回最小弓箭数量：
    当循环遍历完所有气球后，count 记录的就是引爆所有气球所必须射出的最小弓箭数量，直接将其返回即可。

代码

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;
    }
}

第二题：435. 无重叠区间

解题思路

本题的目标是给定一组区间集合 intervals，找出需要移除区间的最小数量，使得剩余区间互不重叠，整体采用了贪心算法的思路，核心在于通过合理的排序和选择策略来确定移除哪些区间，以下是详细的思路阐述：

  1. 排序区间集合：
    首先，利用 Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])) 对输入的区间数组 intervals 按照区间的起始值从小到大进行排序。这样做的好处是方便后续按顺序依次检查相邻区间是否重叠，便于进行后续的贪心选择操作。例如，若原区间集合是 [[3, 5], [1, 4]]，排序后变为 [[1, 4], [3, 5]]，更易于处理它们之间的重叠关系。

  2. 初始化移除区间数量计数变量：
    定义一个变量 count 并初始化为 0，它用于记录需要移除的区间数量。初始值设为 0 是因为还未开始检查重叠情况，默认不需要移除任何区间。

  3. 遍历排序后的区间并处理重叠情况：
    通过 for 循环从第二个区间开始（索引 i = 1）遍历整个 intervals 数组。在每次循环中进行以下判断和操作：

    • 判断区间重叠：
      当 intervals[i][0] < intervals[i - 1][1] 时，这意味着当前区间 intervals[i] 的起始值小于前一个区间 intervals[i - 1] 的结束值，也就表明这两个区间存在重叠部分（因为如果不重叠，当前区间的起始值应该大于等于前一个区间的结束值）。
    • 处理重叠区间（贪心策略）：
      一旦发现重叠，按照贪心策略，我们希望保留能让后续区间更不容易重叠的那个区间，所以选择保留结束值较小的区间。这里通过 intervals[i][1] = Math.min(intervals[i][1], intervals[i - 1][1]) 来更新当前区间的结束值为两个区间结束值中的较小值，相当于让当前区间 “收缩”，使其更有可能与后面的区间不重叠。同时，将 count 的值加 1，表示发现了一组重叠区间，需要移除一个区间，这里我们默认移除当前区间（其实移除哪个都可以，只要保证最终剩余区间互不重叠且移除数量最少即可，按照这种贪心策略选择移除当前区间便于代码实现）。

  4. 返回移除区间的最小数量：
    当遍历完所有区间后，count 变量记录的就是经过上述处理后，为了让剩余区间互不重叠所需要移除的区间数量，直接将其返回即可。

 代码

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

第三题：763.划分字母区间

解题思路

本题要求对给定的字符串 s 进行划分，使得划分出的片段尽可能多，且每个字母最多出现在一个片段中，解题思路基于贪心算法，通过记录每个字母出现的最远位置来确定划分的片段边界，以下是详细说明：

  1. 整体思路：
    首先需要知道每个字母在字符串中出现的最远距离，然后从字符串开头开始遍历，不断更新当前片段中字母出现的最远距离，当遍历到的位置正好是当前片段中所有字母出现的最远距离时，就说明可以划分出一个片段了，记录下这个片段的长度，接着继续往后遍历确定下一个片段，以此类推，最终得到所有划分片段的长度列表。

  2. 记录每个字母的最远位置：
    创建一个长度为 26 的整数数组 edge，用于记录每个小写英文字母（因为总共 26 个小写英文字母）在字符串中出现的最远位置。通过 char[] chars = s.toCharArray(); 将输入的字符串 s 转换为字符数组，方便遍历每个字符。然后通过循环 for(int i = 0; i < chars.length; i++) 遍历字符数组，对于每个字符 chars[i]，计算它在 edge 数组中的对应位置（通过 chars[i] - 'a'，利用字符的 ASCII 码差值来确定在 edge 数组中的下标），并将其最远位置记录下来，即 edge[chars[i] - 'a'] = i;，如果后面还有相同字母出现且位置更远，就会更新这个最远位置值。

  3. 遍历字符串确定划分片段：
    初始化两个变量，index 用于记录当前片段中字母出现的最远位置，初始值设为 0；last 用于记录上一个划分片段的结束位置，初始值设为 -1。接着通过 for 循环再次遍历字符数组（索引为 i，循环条件是 i < chars.length），在循环中进行以下操作：

    • 更新当前片段的最远位置：
      每次循环都通过 index = Math.max(index, edge[chars[i] - 'a']) 来更新 index 的值，也就是取当前记录的最远位置和当前字符对应的最远位置中的较大值，确保 index 始终是当前片段中所有字母出现的最远位置。
    • 确定划分片段并记录长度：
      当 i == index 时，说明已经遍历到了当前片段中所有字母出现的最远位置，此时可以划分出一个片段了。通过 list.add(i - last) 将当前片段的长度（当前位置 i 减去上一个片段结束位置 last）添加到结果列表 list 中，然后更新 last 的值为当前位置 i，表示上一个片段结束位置更新为当前划分好的片段的结束位置，继续循环去确定下一个片段。

  4. 返回划分片段长度列表：
    当整个字符串遍历结束后，list 中存储的就是所有划分片段的长度，直接将 list 返回即可，这个列表满足题目要求，即每个字母最多出现在一个片段中，且划分的片段数量尽可能多。

代码

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new LinkedList<>();
        int[] edge = new int[26];
        char[] chars = s.toCharArray();
        for(int i = 0;i < chars.length;i++){
            edge[chars[i] - 'a'] = i;
        }
        int index = 0;
        int last = -1;
        for(int i = 0;i < chars.length;i++){
            index = Math.max(index,edge[chars[i] - 'a']);
            if(i == index){
                list.add(i - last);
                last = i;
            }
        }
        return list;
    }
}

 

 

 


原文地址：https://blog.csdn.net/m0_72789504/article/details/144117998

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024