Java C++題解leetcode1620網(wǎng)絡(luò)信號最好的坐標(biāo)

更新時間：2023年01月16日 14:25:54 作者：AnjaVon

這篇文章主要為大家介紹了Java C++題解leetcode1620網(wǎng)絡(luò)信號最好的坐標(biāo)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

題目

題目要求

思路：暴力模擬

因為數(shù)據(jù)范圍小，所以是萬萬沒想到的逐個遍歷……
遍歷每個塔，然后找每個塔輻射的范圍，用一個大矩陣記錄每個點對應(yīng)的信號大小，同時維護當(dāng)前最大的信號及其對應(yīng)坐標(biāo)。

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
    }
}