宫水三叶的刷题日记

V1

2022/11/02阅读:11主题:全栈蓝

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,取值均不超过

因此我们可以直接采用「模拟」的方式进行求解,而不会面临 TLEMLE 的风险。

具体的,我们建立一个大小为 的棋盘 g,用于记录每个坐标点的信号值,即 代表坐标 的信号值为

其中 的大小是利用了「任意坐标 的取值范围不超过 」,同时「最远距离 不超过 」并且「最终答案为非负坐标」而定。

随后,我们可以枚举所有 ,并检查以该塔为中心点,大小为 的矩阵中的所有点(该塔所能贡献信号的所有坐标均落在矩阵中),枚举过程中使用变量 val 记录最大信号值,使用 xy 记录答案坐标。

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 = 000
        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 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1