宫水三叶的刷题日记
2022/11/02阅读：21主题：全栈蓝
1620. 网络信号最好的坐标 : 枚举运用题
题目描述
这是 LeetCode 上的 「1620. 网络信号最好的坐标」 ，难度为 「中等」。
Tag : 「模拟」、「枚举」
给你一个数组 towers 和一个整数 radius 。
数组 towers 中包含一些网络信号塔，其中
表示第 i 个网络信号塔的坐标是
且信号强度参数为
。所有坐标都是在 X-Y 坐标系内的 「整数」 坐标。两个坐标之间的距离用 「欧几里得距离」 计算。
整数 radius 表示一个塔 能到达 的 最远距离 。如果一个坐标跟塔的距离在 radius 以内，那么该塔的信号可以到达该坐标。在这个范围以外信号会很微弱，所以 radius 以外的距离该塔是 不能到达的 。
如果第 i 个塔能到达
，那么该塔在此处的信号为 ⌊q / (1 + d)⌋ ，其中 d 是塔跟此坐标的距离。一个坐标的 信号强度 是所有 能到达 该坐标的塔的信号强度之和。
请你返回数组 ，表示 信号强度 最大的 整数 坐标点 。如果有多个坐标网络信号一样大，请你返回字典序最小的 「非负」 坐标。
注意：
-
坐标 (x1, y1)字典序比另一个坐标(x2, y2)小，需满足以下条件之一：-
要么 x1 < x2， -
要么 x1 == x2且y1 < y2。
-
-
⌊val⌋表示小于等于val的最大整数（向下取整函数）。
示例 1： 
输入：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：
输入：towers = [[23,11,21]], radius = 9
输出：[23,11]
解释：由于仅存在一座信号塔，所以塔的位置信号强度最大。
示例 3：
输入：towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2
输出：[1,2]
解释：坐标 (1, 2) 的信号强度最大。
提示：
模拟
观察数据范围：无论是 towers 数组大小、坐标
的值域大小，还是最远距离 k = radius，取值均不超过
。
因此我们可以直接采用「模拟」的方式进行求解，而不会面临 TLE 或 MLE 的风险。
具体的，我们建立一个大小为
的棋盘 g，用于记录每个坐标点的信号值，即
代表坐标
的信号值为
。
❝其中 的大小是利用了「任意坐标 的取值范围不超过 」，同时「最远距离 不超过 」并且「最终答案为非负坐标」而定。
❞
随后，我们可以枚举所有
，并检查以该塔为中心点，大小为
的矩阵中的所有点（该塔所能贡献信号的所有坐标均落在矩阵中），枚举过程中使用变量 val 记录最大信号值，使用 x 和 y 记录答案坐标。
Java 代码：
class 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 代码：
function 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 代码：
class 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]
-
时间复杂度：需要 的复杂度枚举所有的塔 ；对于每座塔，我们需要枚举以该塔为中心点，大小为 的矩阵中的所有坐标。整体复杂度为 -
空间复杂度： ，其中 为棋盘大小
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1620 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉
作者介绍