开发者

Java C++题解leetcode764最大加号标志示例

开发者 https://www.devze.com 2023-01-17 10:39 出处:网络 作者: AnjaVon
目录题目思路:前缀和JavaC++Rust总结题目 题目链接 思路:前缀和 Java class Solution {
目录
  • 题目
  • 思路:前缀和
    • Java
    • C++
    • Rust
  • 总结

    题目

    题目链接

    Java C++题解leetcode764最大加号标志示例

    Java C++题解leetcode764最大加号标志示例

    Java C++题解leetcode764最大加号标志示例

    思路:前缀和

    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 - javascriptj] = 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(Mat开发者_JS培训h.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 +php 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])));
                }
    javascript        }
            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
        }
    }
    
    • 时间复杂度:O(n^2)
    • 空间复杂度:O(n^2)

    编程客栈

    意外的前缀和,本来想用DFS的;

    还是蛮快乐的模拟题~

    以上就是Java C++题解leetcode764最大加号标志示例的详细内容,更多关于Java C++php题解最大加号标志的资料请关注我们其它相关文章!

    0

    精彩评论

    暂无评论...
    验证码 换一张
    取 消

    关注公众号