Java?C++題解leetcode764最大加號標志示例

更新時間：2023年01月16日 11:37:03 作者：AnjaVon

這篇文章主要為大家介紹了Java?C++題解leetcode764最大加號標志示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

題目

題目鏈接

思路：前綴和

Java

class Solution {
    public int orderOfLargestPlusSign(int n, int[][] mines) {
        // 構建網格與雷
        int[][] grid = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++)
            Arrays.fill(grid[i], 1);
        for (var m : mines)
            grid[m[0] + 1][m[1] + 1] = 0;
        // 上下左右前綴和
        int[][] up = new int[n + 10][n + 10], down = new int[n + 10][n + 10], left = new int[n + 10][n + 10], right = new int[n + 10][n + 10];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (grid[i][j] == 1){
                    right[i][j] = right[i - 1][j] + 1;
                    down[i][j] = down[i][j - 1] + 1;
                }
                if (grid[n + 1 - i][n + 1 - j] == 1) {
                    left[n + 1 - i][n + 1 - j] = left[n + 2 - i][n + 1 - j] + 1;
                    up[n + 1 - i][n + 1 - j] = up[n + 1 - i][n + 2 - j] + 1;
                }
            }
        }
        // 找答案，四方向上的最小值即為當前點的十字大小
        int res = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                res = Math.max(res, Math.min(Math.min(right[i][j], down[i][j]), Math.min(left[i][j], up[i][j])));
            }
        }
        return res;
    }
}

時間復雜度：O(n^2)
空間復雜度：O(n^2)

C++

class Solution {
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        // 構建網格與雷
        int grid[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                grid[i][j] = 1;
            }
        }
        for (auto m : mines)
            grid[m[0] + 1][m[1] + 1] = 0;
        // 上下左右前綴和
        int up[n + 10][n + 10], down[n + 10][n + 10], left[n + 10][n + 10], right[n + 10][n + 10];
        memset(up, 0, sizeof(up));
        memset(down, 0, sizeof(down));
        memset(left, 0, sizeof(left));
        memset(right, 0, sizeof(right));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (grid[i][j] == 1){
                    right[i][j] = right[i - 1][j] + 1;
                    down[i][j] = down[i][j - 1] + 1;
                }
                if (grid[n + 1 - i][n + 1 - j] == 1) {
                    left[n + 1 - i][n + 1 - j] = left[n + 2 - i][n + 1 - j] + 1;
                    up[n + 1 - i][n + 1 - j] = up[n + 1 - i][n + 2 - j] + 1;
                }
            }
        }
        // 找答案，四方向上的最小值即為當前點的十字大小
        int res = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                res = max(res, min(min(right[i][j], down[i][j]), min(left[i][j], up[i][j])));
            }
        }
        return res;
    }
};

時間復雜度：O(n^2)
空間復雜度：O(n^2)

Rust

impl Solution {
    pub fn order_of_largest_plus_sign(n: i32, mines: Vec<Vec<i32>>) -> i32 {
        // 構建網格與雷
        let n = n as usize;
        let mut grid = vec![vec![1; n + 1]; n + 1];
        mines.iter().for_each(|m| grid[m[0] as usize + 1][m[1] as usize + 1] = 0);
        // 上下左右前綴和
        let (mut up, mut down, mut left, mut right) = (vec![vec![0; n + 10]; n + 10], vec![vec![0; n + 10]; n + 10], vec![vec![0; n + 10]; n + 10], vec![vec![0; n + 10]; n + 10]);
        for i in 1..=n {
            for j in 1..=n {
                if (grid[i][j] == 1){
                    right[i][j] = right[i - 1][j] + 1;
                    down[i][j] = down[i][j - 1] + 1;
                }
                if (grid[n + 1 - i][n + 1 - j] == 1) {
                    left[n + 1 - i][n + 1 - j] = left[n + 2 - i][n + 1 - j] + 1;
                    up[n + 1 - i][n + 1 - j] = up[n + 1 - i][n + 2 - j] + 1;
                }
            }
        }
        // 找答案，四方向上的最小值即為當前點的十字大小
        let mut res = 0;
        for i in 1..=n {
            for j in 1..=n {
                res = res.max(right[i][j].min(left[i][j]).min(down[i][j].min(up[i][j])));
            }
        }
        res
    }
}