目录题目思路:前缀和Javac++Rust总结题目 题目链接 思路:前缀和 从四个方向分别处理网格内连续111的数量,然后遍历每一个点上能构成的十字大小。构建四个矩阵upu
题目链接
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;
}
}
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;
}
};
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
}
}
意外的前缀和,本来想用DFS的;
还是蛮快乐的模拟题~
以上就是Java C++题解LeetCode764最大加号标志示例的详细内容,更多关于Java C++题解最大加号标志的资料请关注编程网其它相关文章!
--结束END--
本文标题: JavaC++题解leetcode764最大加号标志示例
本文链接: https://www.lsjlt.com/news/177890.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0