5936. 引爆最多的炸弹

题目地址(5936. 引爆最多的炸弹)

https://leetcode-cn.com/problems/detonate-the-maximum-bombs/

题目描述

给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。

炸弹用一个下标从 0 开始的二维整数数组 bombs 表示,其中 bombs[i] = [xi, yi, ri] 。xi 和 yi 表示第 i 个炸弹的 X 和 Y 坐标,ri 表示爆炸范围的 半径 。

你需要选择引爆 一个 炸弹。当这个炸弹被引爆时,所有 在它爆炸范围内的炸弹都会被引爆,这些炸弹会进一步将它们爆炸范围内的其他炸弹引爆。

给你数组 bombs ,请你返回在引爆 一个 炸弹的前提下,最多 能引爆的炸弹数目。

 

示例 1:

输入:bombs = [[2,1,3],[6,1,4]]
输出:2
解释:
上图展示了 2 个炸弹的位置和爆炸范围。
如果我们引爆左边的炸弹,右边的炸弹不会被影响。
但如果我们引爆右边的炸弹,两个炸弹都会爆炸。
所以最多能引爆的炸弹数目是 max(1, 2) = 2 。


示例 2:

输入:bombs = [[1,1,5],[10,10,5]]
输出:1
解释:
引爆任意一个炸弹都不会引爆另一个炸弹。所以最多能引爆的炸弹数目为 1 。


示例 3:

输入:bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
输出:5
解释:
最佳引爆炸弹为炸弹 0 ,因为:
- 炸弹 0 引爆炸弹 1 和 2 。红色圆表示炸弹 0 的爆炸范围。
- 炸弹 2 引爆炸弹 3 。蓝色圆表示炸弹 2 的爆炸范围。
- 炸弹 3 引爆炸弹 4 。绿色圆表示炸弹 3 的爆炸范围。
所以总共有 5 个炸弹被引爆。


 

提示:

1 <= bombs.length <= 100
bombs[i].length == 3
1 <= xi, yi, ri <= 105

前置知识

  • BFS

公司

  • 暂无

思路

刚开始的想法是计算图的最大联通分量,因此使用并查集就可以解决。

后来提交的时候发现有问题。这是因为题目限制了引爆关系指的是:某一个炸弹的引爆范围是否会引爆到其他炸弹的圆心,而不是相交就行。这提示了我们:炸弹 a 引爆炸弹 b 的情况下,炸弹 b 不一定能够引爆炸弹 a

也就是说我们将炸弹看做是点,炸弹 a 如果能够引爆炸弹 b,那么就有一条从 a 到 b 的边。而并查集无法处理这种关系。

因此我们可以使用 BFS 来做。首先预处理出图,然后对于图中每一点 i 进行 BFS,然后在这 n 次 bfs 中将最大引爆炸弹数记录下来返回即可。

关键点

  • BFS

代码

  • 语言支持:Python3

Python3 Code:




class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        n = len(bombs)
        d = collections.defaultdict(list)
        def overlap(i, j):
            x1, y1, r1 = bombs[i]
            x2, y2, r2 = bombs[j]
            return (x1 - x2) ** 2 + (y1 - y2) ** 2 <= r1 ** 2
        for i in range(n):
            for j in range(i+1, n):
                if overlap(i, j):
                    d[i].append(j)
                if overlap(j, i):
                    d[j].append(i)
        ans = 1
        for i in range(n):
            q = collections.deque([i])
            vis = set()
            count = 0
            while q:
                cur = q.popleft()
                if cur in vis: continue
                vis.add(cur)
                count += 1
                for neibor in d[cur]:
                    q.append(neibor)
            ans = max(ans, count)
        return ans



复杂度分析

令 n 为数组长度。

  • 时间复杂度:$O(n^3)$. 其中建图部分时间复杂度为 $O(n^2)$,。并且由于每个点的出度最多为 n,因此对于每一个点 i BFS 的时间复杂度为 $n^2$,由于一共有 n 个点,因此总时间复杂度为 $O(n^3)$。

  • 空间复杂度:$O(n^3)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。

最后更新于