引爆最多的炸弹
难度:
标签:
题目描述
给你一个炸弹列表。一个炸弹的 爆炸范围 定义为以炸弹为圆心的一个圆。
炸弹用一个下标从 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
代码结果
运行时间: 110 ms, 内存: 16.6 MB
/*
* 思路：
* 1. 使用Java Streams来构建炸弹之间的关系图。
* 2. 对于每一个炸弹，使用递归Stream计算它可以引爆的最大炸弹数。
* 3. 通过reduce找到最大值。
*/
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;
public class Solution {
public int maximumDetonation(int[][] bombs) {
int n = bombs.length;
List<List<Integer>> graph = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// 构建图
IntStream.range(0, n).forEach(i -> {
IntStream.range(0, n).filter(j -> i != j).forEach(j -> {
long dx = bombs[j][0] - bombs[i][0];
long dy = bombs[j][1] - bombs[i][1];
long r = bombs[i][2];
if (dx * dx + dy * dy <= r * r) {
graph.get(i).add(j);
}
});
});
return IntStream.range(0, n).map(i -> dfs(i, graph, new boolean[n])).max().orElse(0);
}
private int dfs(int current, List<List<Integer>> graph, boolean[] visited) {
visited[current] = true;
return graph.get(current).stream().filter(neighbor -> !visited[neighbor])
.mapToInt(neighbor -> dfs(neighbor, graph, visited)).sum() + 1;
}
}解释
方法:
这道题目可以视为图的问题，其中每个炸弹是一个节点，如果一个炸弹可以引爆另一个炸弹，则在这两个炸弹之间存在一条有向边。首先，我们通过计算两个炸弹之间的距离与半径比较，来构建这个有向图的邻接表。接着，从每个节点开始，使用深度优先搜索（DFS）来探索从该节点出发能够到达多少其他节点，即引爆多少其他炸弹。最后，返回能够引爆最多炸弹的数量。
时间复杂度:
O(n^2)
空间复杂度:
O(n^2)
代码细节讲解
🦆
如何根据两个炸弹之间的距离和半径确定它们之间是否存在有向边？
▷🦆
在构建邻接表时，为什么选择列表而不是其他数据结构，例如哈希表或集合？
▷🦆
在进行深度优先搜索（DFS）时，`vis` 集合的作用是什么？如何确保不会重复访问已经引爆的炸弹？
▷