LC 1620. 网络信号最好的坐标
题目描述
这是 LeetCode 上的 1620. 网络信号最好的坐标 ，难度为 中等。
给你一个数组 towers 和一个整数 radius 。
数组 towers 中包含一些网络信号塔，其中 $towers[i] = [x{i}, y{i}, q{i}]$ 表示第 i 个网络信号塔的坐标是 $(x{i}, y{i})$ 且信号强度参数为 $q{i}$ 。所有坐标都是在 X-Y 坐标系内的 整数 坐标。两个坐标之间的距离用 欧几里得距离 计算。
整数 radius 表示一个塔 能到达 的 最远距离 。如果一个坐标跟塔的距离在 radius 以内，那么该塔的信号可以到达该坐标。在这个范围以外信号会很微弱，所以 radius 以外的距离该塔是 不能到达的 。
如果第 i 个塔能到达 $(x, y)$ ，那么该塔在此处的信号为 ⌊q / (1 + d)⌋ ，其中 d 是塔跟此坐标的距离。一个坐标的 信号强度 是所有 能到达 该坐标的塔的信号强度之和。
请你返回数组 $[c{x}, c{y}]$ ，表示 信号强度 最大的 整数 坐标点 $(c{x}, c{y})$ 。如果有多个坐标网络信号一样大，请你返回字典序最小的 非负 坐标。
注意：
- 坐标
(x1, y1)字典序比另一个坐标(x2, y2)小，需满足以下条件之一：- 要么
x1 < x2， - 要么
x1 == x2且y1 < y2。
- 要么
⌊val⌋表示小于等于val的最大整数（向下取整函数）。
示例 1：
1
2
3
4
5
6
7
8
9
10输入：towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2
输出：[2,1]
解释：
坐标 (2, 1) 信号强度之和为 13
- 塔 (2, 1) 强度参数为 7 ，在该点强度为 ⌊7 / (1 + sqrt(0)⌋ = ⌊7⌋ = 7
- 塔 (1, 2) 强度参数为 5 ，在该点强度为 ⌊5 / (1 + sqrt(2)⌋ = ⌊2.07⌋ = 2
- 塔 (3, 1) 强度参数为 9 ，在该点强度为 ⌊9 / (1 + sqrt(1)⌋ = ⌊4.5⌋ = 4
没有别的坐标有更大的信号强度。
示例 2：1
2
3
4
5输入：towers = [[23,11,21]], radius = 9
输出：[23,11]
解释：由于仅存在一座信号塔，所以塔的位置信号强度最大。
示例 3：1
2
3
4
5输入：towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2
输出：[1,2]
解释：坐标 (1, 2) 的信号强度最大。
提示：
- $1 <= towers.length <= 50$
- $towers[i].length = 3$
- $0 <= x{i}, y{i}, q_{i} <= 50$
- $1 <= radius <= 50$
模拟
观察数据范围：无论是 towers 数组大小、坐标 $(x, y)$ 的值域大小，还是最远距离 k = radius，取值均不超过 $50$。
因此我们可以直接采用「模拟」的方式进行求解，而不会面临 TLE 或 MLE 的风险。
具体的，我们建立一个大小为 $110 \times 110$ 的棋盘 g，用于记录每个坐标点的信号值，即 $g[i][j] = x$ 代表坐标 $(i, j)$ 的信号值为 $x$。
其中 $110$ 的大小是利用了「任意坐标 $(x, y)$ 的取值范围不超过 $50$」，同时「最远距离 $k$ 不超过 $50$」并且「最终答案为非负坐标」而定。
随后，我们可以枚举所有 $towers[i] = (a, b, q)$，并检查以该塔为中心点，大小为 $(k + k)^2$ 的矩阵中的所有点（该塔所能贡献信号的所有坐标均落在矩阵中），枚举过程中使用变量 val 记录最大信号值，使用 x 和 y 记录答案坐标。
Java 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public int[] bestCoordinate(int[][] towers, int k) {
int[][] g = new int[110][110];
int x = 0, y = 0, val = 0;
for (int[] t : towers) {
int a = t[0], b = t[1], q = t[2];
for (int i = Math.max(0, a - k); i <= a + k; i++) {
for (int j = Math.max(0, b - k); j <= b + k; j++) {
double d = Math.sqrt((a - i) * (a - i) + (b - j) * (b - j));
if (d > k) continue;
g[i][j] += Math.floor(q / (1 + d));
if (g[i][j] > val) {
x = i; y = j; val = g[i][j];
} else if (g[i][j] == val && (i < x || (i == x && j < y))) {
x = i; y = j;
}
}
}
}
return new int[]{x, y};
}
}
TypeScript 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21function bestCoordinate(towers: number[][], k: number): number[] {
const g = new Array<Array<number>>(110)
for (let i = 0; i < 110; i++) g[i] = new Array<number>(110).fill(0)
let x = 0, y = 0, val = 0
for (const t of towers) {
const a = t[0], b = t[1], q = t[2]
for (let i = Math.max(0, a - k); i <= a + k; i++) {
for (let j = Math.max(0, b - k); j <= b + k; j++) {
const d = Math.sqrt((a - i) * (a - i) + (b - j) * (b - j))
if (d > k) continue
g[i][j] += Math.floor(q / (1 + d))
if (g[i][j] > val) {
x = i; y = j; val = g[i][j]
} else if (g[i][j] == val && ((i < x) || (i == x && j < y))) {
x = i; y = j
}
}
}
}
return [x, y]
}
Python 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution:
def bestCoordinate(self, towers: List[List[int]], k: int) -> List[int]:
g = [[0] * 110 for _ in range(110)]
x, y, val = 0, 0, 0
for (a, b, q) in towers:
for i in range(max(0, a - k), a + k + 1):
for j in range(max(0, b - k), b + k + 1):
d = math.sqrt((a - i) * (a - i) + (b - j) * (b - j))
if d > k:
continue
g[i][j] += int(q / (1 + d))
if g[i][j] > val:
val, x, y = g[i][j], i, j
elif g[i][j] == val and ((i < x or (i == x and j < y))):
x, y = i, j
return [x, y]
- 时间复杂度：需要 $O(n)$ 的复杂度枚举所有的塔 $towers[i]$；对于每座塔，我们需要枚举以该塔为中心点，大小为 $(k + k)^2$ 的矩阵中的所有坐标。整体复杂度为 $O(n \times k^2)$
- 空间复杂度：$O(M^2)$，其中 $M = 110$ 为棋盘大小
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1620 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
