题目
思路:前缀和
- 从四个方向分别处理网格内连续111的数量,然后遍历每一个点上能构成的十字大小。
- 构建四个矩阵upupup、、、$$,分别表示向上下左右走过程中连续路过的111的数量;
- 以向上为例,那就用下方格子里的值更新当前值,即up[i][j]=up[i][j+1]+1up[i][j]=up[i][j+1] + 1up[i][j]=up[i][j+1]+1。
- 是一个相对暴力的解法,时空复杂度均为O(n2)O(n^2)O(n2),因为要遍历到每个点,还要存四个矩阵,但数据范围较小(500),所以是可接受的。
- 也可以搞一个三维矩阵,存这五个二维矩阵。
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 } }
- 时间复杂度:O(n^2)
- 空间复杂度:O(n^2)
总结
意外的前缀和,本来想用DFS的;
还是蛮快乐的模拟题~
以上就是Java C++题解leetcode764最大加号标志示例的详细内容,更多关于Java C++题解最大加号标志的资料请关注其它相关文章!
原文地址:https://juejin.cn/post/7163910092272697357