文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個數組 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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/coordinate-with-maximum-network-quality
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 蠻力法，遍歷所有的整數坐標點

class Solution { public:vector<int> bestCoordinate(vector<vector<int>>& towers, int radius) {int n = towers.size();int q[51][51];memset(q, 0, sizeof(q));int maxs = 0, x, y;for(int i = 0; i <= 50; ++i) {for(int j = 0; j <= 50; ++j){for(int k = 0; k < n; ++k){int d = (towers[k][0]-i)*(towers[k][0]-i)+(towers[k][1]-j)*(towers[k][1]-j);if(d > radius*radius)continue;q[i][j] += towers[k][2]/(1+sqrt(d));}if(q[i][j] > maxs){maxs = q[i][j];x = i, y = j;}}}return {x, y};} };

132 ms 8.8 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1620. 网络信号最好的坐标的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。