用最少数量的箭引爆气球【贪心算法】

这篇具有很好参考价值的文章主要介绍了用最少数量的箭引爆气球【贪心算法】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  1. 用最少数量的箭引爆气球
    有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭,若有一个气球的直径的开始和结束坐标为 xstart,xend, 且满足 xstart ≤ x ≤ xend,则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后,可以无限地前进。

给你一个数组 points ,返回引爆所有气球所必须射出的 最小 弓箭数 。
用最少数量的箭引爆气球【贪心算法】,贪心算法文章来源地址https://www.toymoban.com/news/detail-691925.html

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][1], points[i][1]);
            }
        }
        return count;
    }
}

到了这里,关于用最少数量的箭引爆气球【贪心算法】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 用最少数量的箭引爆气球——力扣452

    题目描述 解法一

    2024年02月13日
    浏览(36)
  • Leetcode452. 用最少数量的箭引爆气球

    题目来源:452. 用最少数量的箭引爆气球 题解:用最少数量的箭引爆气球 我们首先随机地射出一支箭,再看一看是否能够调整这支箭地射出位置,使得我们可以引爆更多数目的气球。 如图 1-1 所示,我们随机射出一支箭,引爆了除红色气球以外的所有气球。我们称所有引爆的

    2024年02月06日
    浏览(37)
  • 【Leetcode60天带刷】day35——452. 用最少数量的箭引爆气球,435. 无重叠区间,763.划分字母区间

    ​ 452. 用最少数量的箭引爆气球 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组  points  ,其中 points[i] = [xstart, xend]  表示水平直径在  xstart  和  xend 之间的气球。你不知道气球的确切 y 坐标。 一支弓箭可以沿着 x 轴从不同点  完全垂直  

    2024年02月11日
    浏览(63)
  • 华为OD机试 - 最少数量线段覆盖| 机试题算法思路 【2023】

    华为OD机试 - 简易压缩算法(Python) | 机试题算法思路 【2023】 华为OD机试题 - 获取最大软件版本号(JavaScript) 华为OD机试 - 猜字谜(Python) | 机试题+算法思路 【2023】 华为OD机试 - 删除指定目录(Python) | 机试题算法思路 【2023】 华为OD机试 - 自动曝光(Python) | 机试题算法

    2023年04月25日
    浏览(41)
  • 换零钱II:零钱面值动态变化,class方法自动兑换最少零钱(贪心算法)

    银行现存零钱面值种类动态变化但数量无限,类方法change()完成指定金额的最少零钱个数兑换。   (本笔记适合学透python基本数据结构,熟悉class的基构造,对类内全局变量有一定认的 coder 翻阅) 【学习的细节是欢悦的历程】 Python 官网 :https://www.python.org/ Free :大咖免费“

    2024年02月16日
    浏览(36)
  • 【算法】【Python3、动态规划、贪心、二分查找】力扣1671. 得到山形数组的最少删除次数

    1671. 得到山形数组的最少删除次数 给定一个整数数组 nums ,我们定义该数组为山形数组当且仅当: nums 的长度至少为 3。 存在一个下标 i 满足 0 i len(nums) - 1 且: nums[0] nums[1] ... nums[i - 1] nums[i] nums[i] nums[i + 1] ... nums[len(nums) - 1] 现在,给定整数数组 nums ,我们的目标是将其变为

    2024年01月18日
    浏览(53)
  • 每日一题——LeetCode1189.气球的最大数量

    方法一 个人方法: 统计text字符串中\\\'b\\\'、\\\'a\\\'、\\\'l\\\'、\\\'o\\\'、\\\'n\\\' 这几个字符出现的次数 l和n需要两个才能拼成一个balloon,所以碰到l和o加1,其他字符加2 最后求出出现次数最少的那个字符再除以2就是能拼凑成的单词数量,避免出现小数要使用向下取整 消耗时间和内存情况: 方法

    2024年02月01日
    浏览(34)
  • 引脚数量最少的单片机

    2款SOT23-6封装单片机介绍 PMS150C-U06 整盘单价:¥0.19688,该芯片为中国台湾品牌PADAUK(应广) SQ013L-SOT23-6-TR 整盘单价:¥0.27876,该芯片为国产:holychip(芯圣电子) 上述价格为2024-3-29参考价格,有量的情况下,都可以和厂家谈 有时候我们遇到SOT23-6的,可能不知道是什么器件,如2脚

    2024年04月13日
    浏览(43)
  • 力扣100097. 合法分组的最少组数(哈希+贪心)

    给你一个长度为  n  下标从  0  开始的整数数组  nums  。 我们想将下标进行分组,使得  [0, n - 1]  内所有下标  i  都  恰好  被分到其中一组。 如果以下条件成立,我们说这个分组方案是合法的: 对于每个组  g  ,同一组内所有下标在  nums  中对应的数值都相等。 对

    2024年02月06日
    浏览(36)
  • 华为OD机试 - 最少数量线段覆盖 - 二叉树(Java 2023 B卷 100分 考试抽中题)

    华为OD机试 2023B卷题库疯狂收录中,刷题 点这里

    2024年02月11日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包