2023-05-07：给你一个大小为 n x n 二进制矩阵 grid 。最多只能将一格 0 变成 1 。返回执行此操作后，grid 中最大的岛屿面积是多少？岛屿由一组上、下、左、右四个方向相-Toy模板网

这篇具有很好参考价值的文章主要介绍了2023-05-07：给你一个大小为 n x n 二进制矩阵 grid 。最多只能将一格 0 变成 1 。返回执行此操作后，grid 中最大的岛屿面积是多少？岛屿由一组上、下、左、右四个方向相。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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(n^2)$ ，遍历了三次矩阵，每次遍历的时间复杂度均为 $O(n^2)$ 。

空间复杂度： $O(n^2)$ ，使用了两个二维数组，每个数组都是 $\times 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
}

2023-05-07：给你一个大小为 n x n 二进制矩阵 grid 。最多只能将一格 0 变成 1 。返回执行此操作后，grid 中最大的岛屿面积是多少？岛屿由一组上、下、左、右四个方向相,福大大架构师每日一题,rust,线性代数,golang,算法

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);
}

2023-05-07：给你一个大小为 n x n 二进制矩阵 grid 。最多只能将一格 0 变成 1 。返回执行此操作后，grid 中最大的岛屿面积是多少？岛屿由一组上、下、左、右四个方向相,福大大架构师每日一题,rust,线性代数,golang,算法文章来源地址https://www.toymoban.com/news/detail-677765.html

到了这里，关于2023-05-07：给你一个大小为 n x n 二进制矩阵 grid 。最多只能将一格 0 变成 1 。返回执行此操作后，grid 中最大的岛屿面积是多少？岛屿由一组上、下、左、右四个方向相的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！