LeetCode Day 贪心算法第 4 部分

发布日期： 2024-07-09 阅读量： 作者： WBOY

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[][] 点) {
        if(points.length == 0){
            返回0；
        }

        Arrays.sort(点, (a,b) ->{
            如果（a[0] == b[0]）{
                返回a[1] - b[1]；
            }
            返回a[0] - b[0]；
        });

        整数箭头=1；
        int start = 点[0][0];
        int end = 点[0][1];

        for(int i=0; i= 开始 && 点[i][0]<= 结束) ||
            (结束>=点[i][0] && 结束<=点[i][1])){

//将箭头向下缩小 

                if(点[i][0] > 开始 && 点[i][0] <= 结束){
                    开始=点[i][0]；
                }
                if(点[i][1]>开始 && 点[i][1] < 结束){
                    结束=点[i][1]；
                }
                继续;
            }别的{

// 当前箭头点对气球不满意 

                开始=点[i][0]；
                结束=点[i][1]；
                箭头++；   
            }
        }
        返回箭头； 
    }

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 间隔[i].length == 2
-5 * 10^4 原始页面

错误代码

 public int EraseOverlapIntervals(int[][]Intervals) {
        if(intervals.length == 0){
            返回0；
        }

        Arrays.sort(间隔, (a,b) ->{
            if(a[0] == b[0]){
                返回a[1] - b[1]；
            }
            返回a[0] - b[0]；
        });

        Arrays.stream(间隔)
                .map(数组::toString)
                .forEach(System.out::println);

        整数计数=0；

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

        for(int i=1; i=开始 && 间隔[i][0] <结束){
                计数++；
                继续;
            }
            开始=间隔[i][0]；
            结束=间隔[i][1]；
            // list.add(intervals[i]);
        }
        返回计数；
    }

修理它

 public int EraseOverlapIntervals(int[][]Intervals) {
        if(intervals.length == 0){
            返回0；
        }

        Arrays.sort(间隔, (a,b) ->{
            返回a[0] - b[0]；
        });

        整数计数=0；

        int start = 间隔[0][0];
        int end = 间隔[0][1];

        for(int i=1; i


  
  
  763. 分区标签


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

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

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

示例1：

输入：s = "ababcbacadefegdehijhklij"

输出：[9,7,8]

说明：

分区是“ababcbaca”、“defegde”、“hijhklij”。

这是一个分区，以便每个字母最多出现在一个部分中。

像“ababcbacadefegde”、“hijhklij”这样的分区是不正确的，因为它将 s 分成更少的部分。

示例2：

输入：s = "eccbbbbdec"

输出：[10]

限
制：

1 
s 由小写英文字母组成。

原始页面


 public ListpartitionLabels(String s) {
        List list = new ArrayList<>();
        Set<字符> set = new HashSet<>();

        if(s.length() == 0){
            返回列表；
        }

        int 开始 = 0;
        整数结束= 0；
        for(int i=0; ii;j--){
                    if(s.charAt(j) == 目标){
                        休息;
                    }
                }
                结束 = Math.max(结束, j);
            }
            如果（我==结束）{
                list.add(结束-开始+1);
                开始 = i+1;
                设置.clear();
            } 
        }
        返回列表；
    }






 public ListpartitionLabels(String s) {
        List list = new ArrayList<>();
        Set<字符> set = new HashSet<>();

        int[] pos = 新 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){
            返回列表；
        }

        int 开始 = 0;
        整数结束= 0；
        for(int i=0; i





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

        int[] pos = 新 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){
            返回列表；
        }

        int 开始 = 0;
        整数结束= 0；
        for(int i=0; i



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

上一篇: 字符串和字符文字之间的区别

下一篇: 懂车帝官网入口汽车平台懂车帝网页版访问入口地址

LeetCode Day 贪心算法 第 4 部分

随便看看

南昌壹佳企网络通信有限公司

LeetCode Day 贪心算法第 4 部分