LeetCode 题解工作台
引爆最多的炸弹
给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。 炸弹用一个下标从 0 开始的二维整数数组 bombs 表示，其中 bombs[i] = [x i , y i , r i ] 。 x i 和 y i 表示第 i 个炸弹的 X 和 Y 坐标， r i 表示爆炸范围的 半径 。 你需…
6
题型
5
代码语言
3
相关题
当前训练重点
中等 · 图·DFS·traversal
答案摘要
我们定义一个长度为 的数组 ，其中 表示炸弹 的爆炸范围内可以引爆的所有炸弹的下标。 然后，我们遍历所有炸弹，对于两个炸弹 $(x_1, y_1, r_1)$ 和 $(x_2, y_2, r_2)$，我们计算它们之间的距离 $\textit{dist} = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$。如果 $\textit{dist} \leq r_1$，那么…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。
炸弹用一个下标从 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 <= 100bombs[i].length == 31 <= xi, yi, ri <= 105
解题思路
方法一：BFS
我们定义一个长度为 的数组 ，其中 表示炸弹 的爆炸范围内可以引爆的所有炸弹的下标。
然后，我们遍历所有炸弹，对于两个炸弹 和 ，我们计算它们之间的距离 。如果 ，那么炸弹 的爆炸范围内可以引爆炸弹 ，我们就将 添加到 中。如果 ，那么炸弹 的爆炸范围内可以引爆炸弹 ，我们就将 添加到 中。
接下来，我们遍历所有炸弹，对于每个炸弹 ，我们使用广度优先搜索计算炸弹 的爆炸范围内可以引爆的所有炸弹的下标，并记录下来。如果这些炸弹的数量等于 ，那么我们就可以引爆所有炸弹，直接返回 。否则，我们记录下来这些炸弹的数量，并返回最大值。
时间复杂度 ，空间复杂度 。其中 为炸弹的数量。
class Solution:
def maximumDetonation(self, bombs: List[List[int]]) -> int:
n = len(bombs)
g = [[] for _ in range(n)]
for i in range(n - 1):
x1, y1, r1 = bombs[i]
for j in range(i + 1, n):
x2, y2, r2 = bombs[j]
dist = hypot(x1 - x2, y1 - y2)
if dist <= r1:
g[i].append(j)
if dist <= r2:
g[j].append(i)
ans = 0
for k in range(n):
vis = {k}
q = [k]
for i in q:
for j in g[i]:
if j not in vis:
vis.add(j)
q.append(j)
if len(vis) == n:
return n
ans = max(ans, len(vis))
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2) for graph construction and O(n*(n+n)) for DFS across n bombs, leading to roughly O(n^2). Space complexity is O(n^2) for the adjacency graph plus O(n) for DFS recursion stack. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask how to represent bomb interactions efficiently as a graph.
- question_mark
Check if the candidate considers chain reactions via depth-first traversal.
- question_mark
Probe for optimizations to reduce unnecessary repeated DFS computations.
常见陷阱
外企场景- error
Not modeling the problem as a graph and attempting range checks repeatedly.
- error
Ignoring cycles or revisiting bombs in DFS, leading to incorrect counts.
- error
Failing to compute maximum across all starting bombs rather than just one path.
进阶变体
外企场景- arrow_right_alt
Consider limiting detonations to bombs within a certain Manhattan distance instead of Euclidean radius.
- arrow_right_alt
Calculate minimum number of initial detonations required to trigger all bombs.
- arrow_right_alt
Determine which bombs trigger the same maximum chain and report all starting options.