Java C++题解leetcode764最大加号标志示例
AnjaVon 人气:0题目
思路:前缀和
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的;
还是蛮快乐的模拟题~
加载全部内容