題目描述
這是 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 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。
在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)