Java C++题解leetcode1620网络信号最好的坐标
目录
- 题目
- 思路:暴力模拟
- Java
- C++
- Rust
题目
思路:暴力模拟
- 因为数据范围小,所以是万万没想到的逐个遍历……
- 遍历每个塔,然后找每个塔辐射的范围,用一个大矩阵记录每个点对应的信号大小,同时维护当前最大的信号及其对应坐标。
Java
class Solution { public int[] bestCoordinate(int[][] towers, int radius) { int[][] grid = new int[110][110]; int cx = 0, cy = 0, qua = 0; for (int[] t : towers) { int x = t[0], y = t[1], q = t[2]; for (int i = Math.max(0, x - radius); i <= x + radius; i++) { // 从左到右 for (int j = Math.max(0, y - radius); j <= y + radius; j++) { // 从上到下 double d = Math.sqrt((x - i) * (x - i) + (y - j) * (y - j)); // 欧几里得距离 if (d > radius) // 距离超半径 continue; grid[i][j] += Math.floor(q / (1 + d)); if (grid[i][j] > qua) { // 信号更强 cx = i; cy = j; qua = grid[i][j]; } else if (grid[i][j] == qua && (i < cx || (i == cx && j < cy))) { // 字典序更小 cx = i; cy = j; } } } } return new int[] {cx, cy}; } }
C++
- 要初始化啊!这可是C++!
class Solution { public: vector<int> bestCoordinate(vector<vector<int>>& towers, int radius) { int grid[110][110] = {0}; int cx = 0, cy = 0, qua = 0; for (auto t : towers) { int x = t[0], y = t[1], q = t[2]; for (int i = max(0, x - radius); i <= x + radius; i++) { // 从左到右 for (int j = max(0, y - radius); j <= y + radius; j++) { // 从上到下 double d = sqrt((x - i) * (x - i) + (y - j) * (y - j)); // 欧几里得距离 if (d > radius) // 距离超半径 continue; grid[i][j] += floor(q / (1 + d)); if (grid[i][j] > qua) { // 信号更强 cx = i; cy = j; qua = grid[i][j]; } else if (grid[i][j] == qua && (i < cx || (i == cx && j < cy))) { // 字典序更小 cx = i; cy = j; } } } } return {cx, cy}; } };
Rust
impl Solution { pub fn best_coordinate(towers: Vec<Vec<i32>>, radius: i32) -> Vec<i32> { let (mut res, mut qua) = (vec![0; 2], 0); for i in 0..=50 { for j in 0..=50 { let mut q = 0; for t in towers.iter() { let d = ((t[0] - i as i32) as f64).hypot((t[1] - j as i32) as f64); if d <= radius as f64 { q += ((t[2] as f64) / (1 as f64 + d)).floor() as i32; } } if q > qua || (q == qua && (i < res[0] || i == res[0] && j < res[1])) { qua = q; res = vec![i, j]; } } } res } }
以上就是Java C++题解leetcode1620网络信号最好的坐标的详细内容,更多关于Java C++网络信号最好坐标的资料请关注我们其它相关文章!
赞 (0)