首页 > 其他分享 >贪心-用最少的箭射球

贪心-用最少的箭射球

时间:2024-09-10 23:20:12浏览次数:10  
标签:count arr int 射球 最少 弓箭 xend 气球 贪心

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

给你一个数组 points ,其中 points [i] = [xstart,xend] ,返回引爆所有气球所必须射出的最小弓箭数。

示例 1:

  • 输入:points = [[10,16],[2,8],[1,6],[7,12]]
  • 输出:2
  • 解释:对于该样例,x = 6 可以射爆 [2,8],[1,6] 两个气球,以及 x = 11 射爆另外两个气球

重点:

1.局部最优:每支箭都能射中交集最多的球;整体最优:用最少的箭射中所有的球

2.如何避免重复射到球:将球的边界缩小为交集的边界,即两个球的右边界的较小者

public static void main(String[] args) {
        int[][] a ={{10,16},{2,8},{1,6},{7,12}};
        System.out.println(shejian(a));
    }
    public static int shejian(int[][] arr){
        int count = 1;
        Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0]));
        for (int i = 1; i < arr.length; i++) {
            if (arr[i][0] > arr[i - 1][1]){
                count++;
            }else {
                arr[i][1] = Math.min(arr[i][1], arr[i - 1][1]);
                //记录右边界--球能打到的最远地方,第二个的起始点避免重复射箭
            }
        }
        return count;
    }

标签:count,arr,int,射球,最少,弓箭,xend,气球,贪心
From: https://blog.csdn.net/2302_79400545/article/details/142108929

相关文章

  • 数组与贪心算法——179、56、57、228(2简2中)
    179.最大数(简单)给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。解法一、自定义比较器大的排前面然后进行一个比较jpg一开始想的其实是字典序,但是测试里就败了。例如3,3......
  • 数组与贪心算法——452、435、646、406、169(1简4中)
    452.用最少数量的箭引爆气球(中等)有一些球形气球贴在一堵用XY平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i]=[xstart,xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切y坐标。一支弓箭可以沿着x轴从不同点 完全......
  • 每日OJ_牛客_最长递增子序列(dp/贪心模板)
    目录牛客_最长递增子序列(dp/贪心模板)解析代码牛客_最长递增子序列(dp/贪心模板)最长公共子序列__牛客网解析代码在一个序列中找最长递增子序列,动态规划的典型应用,下面是两个模版CISdp模板:#include<iostream>#include<vector>usingnamespacestd;intLIS(vect......
  • 1.2贪心算法
    算法理解每次做决策时总是采取当前最优策略,从局部最优到整体最优贪心的证明呜呜呜,我不会贪心的特征1.贪心选择特征每次选择可能依赖于以前的选择但不依赖于后面的选择,要证明它,就要证明它满足局部最优到整体最优,好像又证回去了2.最优子结构性质一个问题的最优解包含其子问......
  • 力扣-968监控二叉树(Java贪心详细题解)
    题目链接:968.监控二叉树-力扣(LeetCode)前情提要:本题是一道名副其实的hard题目,他考察二叉树和贪心的综合运用能力。所以我们不仅要会贪心还要会二叉树的一些知识,如果没有写二叉树类型的题目,建议大家该题可以放放,去刷其他的题目。因为本人最近都来刷贪心类的题目所以该......
  • [蓝桥杯 2018 省 A] 付账问题--贪心题解
    题目重述:[蓝桥杯2018省A]付账问题-洛谷#[蓝桥杯2018省A]付账问题##题目描述几个人一起出去吃饭是常有的事。但在结帐的时候,常常会出现一些争执。现在有$n$个人出去吃饭,他们总共消费了$S$元。其中第$i$个人带了$a_i$元。幸运的是,所有人带的钱的总数是......
  • 452. 用最少数量的箭引爆气球
    有一些球形气球贴在一堵用XY平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i]=[xstart,xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切y坐标。一支弓箭可以沿着x轴从不同点 完全垂直 地射出。在坐标 x 处射出一支......
  • 1312. 让字符串成为回文串的最少插入次数
    1312.让字符串成为回文串的最少插入次数给你一个字符串s,每一次操作你都可以在字符串的任意位置插入任意字符。请你返回让s成为回文串的最少操作次数。「回文串」是正读和反读都相同的字符串。示例1:输入:s="zzazz"输出:0解释:字符串"zzazz"已经是回文串了,所......
  • 【3.5】贪心算法-解优势洗牌(类田忌赛马问题)
    一、问题        给定两个大小相等的数组A和B,A相对于B的优势可以用满足A[i]>B[i]的索引i的数目来描述。返回A的任意排列,使其相对于B的优势最大化。二、解题思路        这个问题要求我们重新排列数组A,使得在相同位置上,数组A的......
  • 【3.10】贪心算法-找出对应 LCP 矩阵的字符串
    一、题目对任一由n个小写英文字母组成的字符串word,我们可以定义一个nxn的矩阵,并满足:lcp[i][j]等于子字符串 word[i,...,n-1]和word[j,...,n-1]之间的最长公共前缀的长度。给你一个nxn的矩阵lcp。返回与lcp对应的、按字典序最小的字符串 word。如果......