1
2023-05-07：给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。 返回执行此操作后，grid 中最大的岛屿面积是多少？ 岛屿 由一组上、下、左、右四个方向相
作者：福大大架构师每日一题
- 2023-05-07 北京
本文字数：5103 字
阅读完需：约 17 分钟
2023-05-07：给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
返回执行此操作后，grid 中最大的岛屿面积是多少？
岛屿 由一组上、下、左、右四个方向相连的 1 形成。
输入: grid = [[1, 0], [0, 1]]。
输出: 3。
来自亚马逊、谷歌、微软、Facebook、Bloomberg。
答案 2023-05-07：
算法步骤：
1.遍历输入矩阵 grid，对于每个岛屿进行标记，并用数组 sizes 统计每个岛屿的大小。
2.遍历矩阵 grid，对于每个位置上的值，如果当前位置上的值为非零正整数，则更新答案为当前岛屿的大小。
3.遍历矩阵 grid，当当前位置上的值为 0 时，分别查看该位置上、下、左、右四个方向是否有与其相邻且已经被访问过的岛屿，并将它们的大小累加起来。如果这些岛屿的大小之和加上当前位置上自身的大小可以更新最大岛屿面积，则更新答案。
4.返回答案。
时间复杂度：O(n2) ，遍历了三次矩阵，每次遍历的时间复杂度均为 O(n2)。
空间复杂度：O(n2)，使用了两个二维数组，每个数组都是 n×n 的大小。
go 完整代码如下：
package main
import "fmt"
func main() { grid := [][]int{{1, 0}, {0, 1}} ans := largestIsland(grid) fmt.Println(ans)}
func largestIsland(grid [][]int) int { n := len(grid) m := len(grid[0]) id := 2 for i := 0; i < n; i++ { for j := 0; j < m; j++ { if grid[i][j] == 1 { infect(grid, i, j, id, n, m) id++ } } } sizes := make([]int, id) ans := 0 for i := 0; i < n; i++ { for j := 0; j < m; j++ { if grid[i][j] > 1 { sizes[grid[i][j]]++ ans = max(ans, sizes[grid[i][j]]) } } } visited := make([]bool, id) for i := 0; i < n; i++ { for j := 0; j < m; j++ { if grid[i][j] == 0 { up := 0 if i-1 >= 0 { up = grid[i-1][j] } down := 0 if i+1 < n { down = grid[i+1][j] } left := 0 if j-1 >= 0 { left = grid[i][j-1] } right := 0 if j+1 < m { right = grid[i][j+1] } merge := 1 + sizes[up] visited[up] = true if !visited[down] { merge += sizes[down] visited[down] = true } if !visited[left] { merge += sizes[left] visited[left] = true } if !visited[right] { merge += sizes[right] visited[right] = true } ans = max(ans, merge) visited[up] = false visited[down] = false visited[left] = false visited[right] = false } } } return ans}
func infect(grid [][]int, i, j, v, n, m int) { if i < 0 || i == n || j < 0 || j == m || grid[i][j] != 1 { return } grid[i][j] = v infect(grid, i-1, j, v, n, m) infect(grid, i+1, j, v, n, m) infect(grid, i, j-1, v, n, m) infect(grid, i, j+1, v, n, m)}
func max(a, b int) int { if a > b { return a } return b}
复制代码
rust 完整代码如下：
fn main() { let grid = vec![vec![1, 0], vec![0, 1]]; let ans = largest_island(grid); println!("{}", ans);}
fn largest_island(grid: Vec<Vec<i32>>) -> i32 { let n = grid.len(); let m = grid[0].len(); let mut id = 2; let mut new_grid = grid.clone(); for i in 0..n { for j in 0..m { if new_grid[i][j] == 1 { infect(&mut new_grid, i as i32, j as i32, id, n as i32, m as i32); id += 1; } } } let mut sizes = vec![0; id as usize]; let mut ans = 0; for i in 0..n { for j in 0..m { if new_grid[i][j] > 1 { sizes[new_grid[i][j] as usize] += 1; ans = ans.max(sizes[new_grid[i][j] as usize]); } } } let mut visited = vec![false; id as usize]; for i in 0..n { for j in 0..m { if new_grid[i][j] == 0 { let up = if i > 0 { new_grid[i - 1][j] } else { 0 }; let down = if i < n - 1 { new_grid[i + 1][j] } else { 0 }; let left = if j > 0 { new_grid[i][j - 1] } else { 0 }; let right = if j < m - 1 { new_grid[i][j + 1] } else { 0 }; let mut merge = 1; if up > 0 && !visited[up as usize] { visited[up as usize] = true; merge += sizes[up as usize]; } if down > 0 && !visited[down as usize] { visited[down as usize] = true; merge += sizes[down as usize]; } if left > 0 && !visited[left as usize] { visited[left as usize] = true; merge += sizes[left as usize]; } if right > 0 && !visited[right as usize] { visited[right as usize] = true; merge += sizes[right as usize]; } ans = ans.max(merge); visited[up as usize] = false; visited[down as usize] = false; visited[left as usize] = false; visited[right as usize] = false; } } } ans}
fn infect(grid: &mut Vec<Vec<i32>>, i: i32, j: i32, v: i32, n: i32, m: i32) { if i < 0 || i == n || j < 0 || j == m || grid[i as usize][j as usize] != 1 { return; } grid[i as usize][j as usize] = v; infect(grid, i - 1, j, v, n, m); infect(grid, i + 1, j, v, n, m); infect(grid, i, j - 1, v, n, m); infect(grid, i, j + 1, v, n, m);}
复制代码
c 完整代码如下：
#include <stdio.h>#include <stdbool.h>#include <string.h>#define MAX_SIZE 50
void infect(int grid[][MAX_SIZE], int i, int j, int v, int n, int m);int largestIsland(int grid[][MAX_SIZE], int n, int m);
int main() { int grid[][MAX_SIZE] = { {1, 0}, {0, 1} }; int n = 2; int m = 2; int ans = largestIsland(grid, n, m); printf("%d\n", ans); // 输出 3 return 0;}
int largestIsland(int grid[][MAX_SIZE], int n, int m) { int id = 2; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 1) { infect(grid, i, j, id++, n, m); } } } int sizes[MAX_SIZE * MAX_SIZE]; memset(sizes, 0, sizeof(sizes)); int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] > 1) { ans = ans > ++sizes[grid[i][j]] ? ans : sizes[grid[i][j]]; } } } bool visited[MAX_SIZE * MAX_SIZE] = { false }; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 0) { int up = i - 1 >= 0 ? grid[i - 1][j] : 0; int down = i + 1 < n ? grid[i + 1][j] : 0; int left = j - 1 >= 0 ? grid[i][j - 1] : 0; int right = j + 1 < m ? grid[i][j + 1] : 0; int merge = 1 + sizes[up]; visited[up] = true; if (!visited[down]) { merge += sizes[down]; visited[down] = true; } if (!visited[left]) { merge += sizes[left]; visited[left] = true; } if (!visited[right]) { merge += sizes[right]; visited[right] = true; } ans = ans > merge ? ans : merge; visited[up] = false; visited[down] = false; visited[left] = false; visited[right] = false; } } } return ans;}
void infect(int grid[][MAX_SIZE], int i, int j, int v, int n, int m) { if (i < 0 || i == n || j < 0 || j == m || grid[i][j] != 1) { return; } grid[i][j] = v; infect(grid, i - 1, j, v, n, m); infect(grid, i + 1, j, v, n, m); infect(grid, i, j - 1, v, n, m); infect(grid, i, j + 1, v, n, m);}
复制代码
c++完整代码如下：
#include <iostream>#include <cstring>#define MAX_SIZE 50
using namespace std;
void infect(int grid[][MAX_SIZE], int i, int j, int v, int n, int m);int largestIsland(int grid[][MAX_SIZE], int n, int m);
int main() { int grid[][MAX_SIZE] = { {1, 0}, {0, 1} }; int n = 2; int m = 2; int ans = largestIsland(grid, n, m); cout << ans << endl; return 0;}
int largestIsland(int grid[][MAX_SIZE], int n, int m) { int id = 2; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 1) { infect(grid, i, j, id++, n, m); } } } int sizes[MAX_SIZE * MAX_SIZE]; memset(sizes, 0, sizeof(sizes)); // 初始化为0 int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] > 1) { ans = max(ans, ++sizes[grid[i][j]]); } } } bool visited[MAX_SIZE * MAX_SIZE] = { false }; // 初始化为false for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == 0) { int up = i - 1 >= 0 ? grid[i - 1][j] : 0; int down = i + 1 < n ? grid[i + 1][j] : 0; int left = j - 1 >= 0 ? grid[i][j - 1] : 0; int right = j + 1 < m ? grid[i][j + 1] : 0; int merge = 1 + sizes[up]; visited[up] = true; if (!visited[down]) { merge += sizes[down]; visited[down] = true; } if (!visited[left]) { merge += sizes[left]; visited[left] = true; } if (!visited[right]) { merge += sizes[right]; visited[right] = true; } ans = max(ans, merge); visited[up] = false; visited[down] = false; visited[left] = false; visited[right] = false; } } } return ans;}
void infect(int grid[][MAX_SIZE], int i, int j, int v, int n, int m) { if (i < 0 || i == n || j < 0 || j == m || grid[i][j] != 1) { return; } grid[i][j] = v; infect(grid, i - 1, j, v, n, m); infect(grid, i + 1, j, v, n, m); infect(grid, i, j - 1, v, n, m); infect(grid, i, j + 1, v, n, m);}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 5
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/a5217b572837ffdf3f7863999】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
福大大架构师每日一题
关注
公众号：福大大架构师每日一题 2021-02-15 加入
公众号：福大大架构师每日一题
评论