LeetCode Day 贪心算法 第 4 部分

452. 击破气球的最少箭数

一些球形气球贴在代表 XY 平面的平坦墙壁上。气球表示为 2D 整数数组点，其中，points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend 之间延伸的气球。您不知道气球的确切 y 坐标。

箭头可以从沿 x 轴的不同点直接垂直（沿 y 轴正方向）射出。如果 xstart

给定数组点，返回击破所有气球所需的最少箭数。

示例1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
说明：气球可以用 2 个箭头来爆破：

• 在 x = 6 处射箭，使气球 [2,8] 和 [1,6] 破裂。
• 在 x = 11 处射箭，使气球 [10,16] 和 [7,12] 破裂。 示例2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
说明：每个气球需要射一支箭，总共4支箭。
示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
说明：气球可以用 2 个箭头来爆破：

• 在 x = 2 处射箭，使气球 [1,2] 和 [2,3] 破裂。
• 在 x = 4 处射箭，使气球 [3,4] 和 [4,5] 破裂。

限制：

1 点[i].length == 2
-2^31 原始页面

    public int findMinArrowShots(int[][] points) {
        if(points.length == 0){
            return 0;
        }

        Arrays.sort(points, (a,b) ->{
            if(a[0] == b[0]){
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });

        int arrow = 1;
        int start = points[0][0];
        int end = points[0][1];

        for(int i=0; i<points.length; i++){

            if((points[i][0] >= start && points[i][0]<= end) ||
            (end >=points[i][0] && end <= points[i][1])){

//Narrow the arrow point down 

                if(points[i][0] > start && points[i][0] <= end){
                    start = points[i][0];
                }
                if(points[i][1]>start && points[i][1] < end){
                    end = points[i][1];
                }
                continue;
            }else{

// current arrow point is not satisfied with balloons 

                start = points[i][0];
                end = points[i][1];
                arrow ++;   
            }
        }
        return arrow; 
    }

435. 不重叠的区间

给定一个间隔数组，其中间隔[i] = [starti, endi]，返回需要删除的最小间隔数，以使其余间隔不重叠。

示例1：

输入：间隔 = [[1,2],[2,3],[3,4],[1,3]]
输出：1
解释：[1,3]可以去掉，其余区间不重叠。
示例2：

输入：间隔 = [[1,2],[1,2],[1,2]]
输出：2
解释：您需要删除两个 [1,2] 以使其余间隔不重叠。
示例 3：

输入：间隔 = [[1,2],[2,3]]
输出：0
说明：您不需要删除任何间隔，因为它们已经不重叠。

限制：

1 <= 间隔.长度 <= 10^5
间隔[i].length == 2
-5 * 10^4 <= 起始 <结束 <= 5 * 10^4
原始页面

错误代码

    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length == 0){
            return 0;
        }

        Arrays.sort(intervals, (a,b) ->{
            if(a[0] == b[0]){
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });

        Arrays.stream(intervals)
                .map(Arrays::toString)
                .forEach(System.out::println);

        int count = 0;

        // List<int[]> list = new LinkedList<>();
        int start = intervals[0][0];
        int end = intervals[0][1];

        for(int i=1; i<intervals.length; i++){
            //if the left edge is not included in the previous interval the right will definitely not be in it.
            if(intervals[i][0] >=start && intervals[i][0] <end){
                count++;
                continue;
            }
            start = intervals[i][0];
            end = intervals[i][1];
            // list.add(intervals[i]);
        }
        return count;
    }

修复它

    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length == 0){
            return 0;
        }

        Arrays.sort(intervals, (a,b) ->{
            return a[0] - b[0];
        });

        int count = 0;

        int start = intervals[0][0];
        int end = intervals[0][1];

        for(int i=1; i<intervals.length; i++){
            if(intervals[i][0] < intervals[i-1][1]){
                count++;
                // here we need to find the maximum overlap, the means whether the next element  overlap to above groups of overlaps 
                // if only find overlap from the previous interval, it may cause miss calculation over-add 1 count
                intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);  
            }
        }
        return count;
    }

763. 分区标签

给你一个字符串 s。我们希望将字符串分成尽可能多的部分，以便每个字母最多出现在一个部分中。

请注意，分区的完成是为了将所有部分按顺序连接后，得到的字符串应该是 s。

返回表示这些部分大小的整数列表。

示例1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
说明：
分区是“ababcbaca”、“defegde”、“hijhklij”。
这是一个分区，以便每个字母最多出现在一个部分中。
像“ababcbacadefegde”、“hijhklij”这样的分区是不正确的，因为它将 s 分成更少的部分。
示例2：

输入：s = "eccbbbbdec"
输出：[10]

限制：

1 <= s.length <= 500
s 由小写英文字母组成。
原始页面

    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();
        Set<Character> set = new HashSet<>();

        if(s.length() == 0){
            return list;
        }

        int start = 0;
        int end = 0;
        for(int i=0; i<s.length(); i++){
            Character target = s.charAt(i);

            if(!set.contains(target)){
                set.add(target);
                int j = s.length()-1;
                for(;j>i;j--){
                    if(s.charAt(j) == target){
                        break;
                    }
                }
                end = Math.max(end, j);
            }
            if(i == end){
                list.add(end-start+1);
                start = i+1;
                set.clear();
            } 
        }
        return list;
    }

    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();
        Set<Character> set = new HashSet<>();

        int[] pos = new int[27];

        for(int i=s.length()-1; i>0;i--){
            if(pos[s.charAt(i)-'a'] == 0){
                pos[s.charAt(i)-'a'] = i;
            }
        }

        if(s.length() == 0){
            return list;
        }

        int start = 0;
        int end = 0;
        for(int i=0; i<s.length(); i++){
            Character target = s.charAt(i);

            if(!set.contains(target)){
                set.add(target);

                end = Math.max(end, pos[target-'a']);
            }
            if(i == end){
                list.add(end-start+1);
                start = i+1;
                set.clear();
            } 
        }
        return list;
    }

    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();

        int[] pos = new int[27];

        for(int i=s.length()-1; i>0;i--){
            if(pos[s.charAt(i)-'a'] == 0){
                pos[s.charAt(i)-'a'] = i;
            }
        }

        if(s.length() == 0){
            return list;
        }

        int start = 0;
        int end = 0;
        for(int i=0; i<s.length(); i++){
            Character target = s.charAt(i);

            end = Math.max(end, pos[target-'a']);

            if(i == end){
                list.add(end-start+1);
                start = i+1;
            } 
        }
        return list;
    }

因为判断元素是否已经在集合中并不重要，所以我们只关注是否到达终点，如果出现相同的元素，则终点不会改变，如果不同的元素合并，看起来 end 可能会改变，但所有这些都不会影响 if 评估，因此我们可以删除它们。

以上是LeetCode Day 贪心算法 第 4 部分的详细内容。更多信息请关注PHP中文网其他相关文章！