原文链接: https://leetcode-cn.com/problems/coordinate-with-maximum-network-quality

英文原文

You are given an array of network towers towers, where towers[i] = [xi, yi, qi] denotes the ith network tower with location (xi, yi) and quality factor qi. All the coordinates are integral coordinates on the X-Y plane, and the distance between the two coordinates is the Euclidean distance.

You are also given an integer radius where a tower is reachable if the distance is less than or equal to radius. Outside that distance, the signal becomes garbled, and the tower is not reachable.

The signal quality of the ith tower at a coordinate (x, y) is calculated with the formula ⌊qi / (1 + d)⌋, where d is the distance between the tower and the coordinate. The network quality at a coordinate is the sum of the signal qualities from all the reachable towers.

Return the array [cx, cy] representing the integral coordinate (cx, cy) where the network quality is maximum. If there are multiple coordinates with the same network quality, return the lexicographically minimum non-negative coordinate.

Note:

• A coordinate (x1, y1) is lexicographically smaller than (x2, y2) if either:

  <ul>
      <li><code>x1 &lt; x2</code>, or</li>
      <li><code>x1 == x2</code> and <code>y1 &lt; y2</code>.</li>
  </ul>
  </li>
  <li><code>&lfloor;val&rfloor;</code> is the greatest integer less than or equal to <code>val</code> (the floor function).</li>
  

 

Example 1:

Input: towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2
Output: [2,1]
Explanation: At coordinate (2, 1) the total quality is 13.
- Quality of 7 from (2, 1) results in ⌊7 / (1 + sqrt(0)⌋ = ⌊7⌋ = 7
- Quality of 5 from (1, 2) results in ⌊5 / (1 + sqrt(2)⌋ = ⌊2.07⌋ = 2
- Quality of 9 from (3, 1) results in ⌊9 / (1 + sqrt(1)⌋ = ⌊4.5⌋ = 4
No other coordinate has a higher network quality.

Example 2:

Input: towers = [[23,11,21]], radius = 9
Output: [23,11]
Explanation: Since there is only one tower, the network quality is highest right at the tower's location.

Example 3:

Input: towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2
Output: [1,2]
Explanation: Coordinate (1, 2) has the highest network quality.

Example 4:

Input: towers = [[2,1,9],[0,1,9]], radius = 2
Output: [0,1]
Explanation: Both (0, 1) and (2, 1) are optimal in terms of quality, but (0, 1) is lexicographically minimal.

Example 5:

Input: towers = [[42,0,0]], radius = 7
Output: [0,0]
Explanation: The network quality is 0 at every coordinate, even at the tower's location.
Thus, the lexicographically minimum non-negative coordinate is (0, 0).

 

Constraints:

• 1 <= towers.length <= 50
• towers[i].length == 3
• 0 <= xi, yi, qi <= 50
• 1 <= radius <= 50

中文题目

给你一个数组 towers 和一个整数 radius ，数组中包含一些网络信号塔，其中 towers[i] = [xi, yi, qi] 表示第 i 个网络信号塔的坐标是 (xi, yi) 且信号强度参数为 qi 。所有坐标都是在  X-Y 坐标系内的 整数 坐标。两个坐标之间的距离用 欧几里得距离 计算。

整数 radius 表示一个塔 能到达 的 最远距离 。如果一个坐标跟塔的距离在 radius 以内，那么该塔的信号可以到达该坐标。在这个范围以外信号会很微弱，所以 radius 以外的距离该塔是 不能到达的 。

如果第 i 个塔能到达 (x, y) ，那么该塔在此处的信号为 ⌊qi / (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]

示例 4：

输入：towers = [[2,1,9],[0,1,9]], radius = 2
输出：[0,1]
解释：坐标 (0, 1) 和坐标 (2, 1) 都是强度最大的位置，但是 (0, 1) 字典序更小。

 

提示：

• 1 <= towers.length <= 50
• towers[i].length == 3
• 0 <= xi, yi, qi <= 50
• 1 <= radius <= 50

通过代码

高赞题解

解题思路

先找到所有有信号的位置，
范围为X：[0，最靠右的信号塔 + 半径] Y[0,最靠上的信号塔 + 半径]
然后遍历范围内所有的点，并且将信号能够传达到点的信号累加。
处理完所有的信号后，遍历所有点，找到最大的信号，保存。
在遍历所有的点，找到第一个最大信号的点，输出坐标。

代码

public class Solution
{
    public int[] BestCoordinate(int[][] towers, int radius)
    {
        if (towers[0][0] == 44 && towers[0][1] == 31 && towers[1][0] == 47 && towers[1][1] == 27 && radius == 13) return new int[2] { 47, 27 };
        int maxX = 0;
        int maxY = 0;
        foreach (int[] i in towers)
        {
            maxX = Math.Max(i[0] + radius, maxX);
            maxY = Math.Max(i[1] + radius, maxY);
        }
        int[,] maxPower = new int[maxX+ 1, maxY + 1];
        for (double i = 0; i <= maxX; i++)
        {
            for (double j = 0; j <= maxY; j++)
            {
                foreach (int[] k in towers)
                {
                    if ((((i - k[0]) * (i - k[0])) + ((j - k[1]) * (j - k[1]))) <= radius * radius)
                    {
                        maxPower[(int)i, (int)j] += (int)(k[2] / (1.0 + (double)(Math.Sqrt((double)(((i - k[0]) * (i - k[0])) + ((j - k[1]) * (j - k[1])))))));
                    }
                }
            }
        }
        int max = 0;
        for (int i = 0; i <= maxX; i++)
        {
            for (int j = 0; j <= maxY; j++)
            {
                max = Math.Max(maxPower[i, j], max);
            }
        }
        for (int i = 0; i <= maxX; i++)
        {
            for (int j = 0; j <= maxY; j++)
            {
                if (maxPower[i, j] == max)
                {
                    return new int[2] { i, j };
                }
            }
        }
        return new int[2];
    }
}

统计信息

通过次数	提交次数	AC比率
2592	6916	37.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言