【Day 50 】2022-01-30 - null

[azl397985856]

null

入选理由

暂无

题目地址

null

前置知识

暂无

题目描述

给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 （代表土地） 构成的组合，
这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。
你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。（如果没有岛屿，则返回面积为 0 。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。

示例 2:

[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵，返回 0。

 
注意：给定的矩阵 grid 的长度和宽度都不超过 50

[Toms-BigData]

【Day 50】695. 岛屿的最⼤⾯积

思路

dfs

golang代码

func maxAreaOfIsland(grid [][]int) (ans int) {
    m:=len(grid)
    n:=len(grid[0])
    var dps func(num *int,i,j int)
    dps = func(num *int,i,j int) {
        *num++
        if *num >ans{
            ans = *num
        }
        if i-1>=0&&grid[i-1][j] == 1 {
            grid[i-1][j]-=1
            dps(num, i-1, j)
        }
        if j-1>=0&&grid[i][j-1] == 1 {
            grid[i][j-1] -=1
            dps(num, i, j-1)
        }
        if i+1<m&&grid[i+1][j] == 1 {
            grid[i+1][j] -=1
            dps(num, i+1, j)
        }
        if j+1<n&&grid[i][j+1] == 1 {
            grid[i][j+1] -=1
            dps(num, i, j+1)
        }
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1{
                num:=0
                grid[i][j]-=1
                dps(&num, i, j)
            }
        }
    }
    return
}

复杂度

时间复杂度：O(R×C)。其中 R 是给定网格中的行数，C 是列数。我们访问每个网格最多一次。 空间复杂度：O(R×C)，递归的深度最大可能是整个网格的大小，因此最大可能使用O(R×C) 的栈空间。

[hx-code]

var maxAreaOfIsland = function(grid) { let x=grid[0].length,y=grid.length; let res=0; function dfs(i,j){ // i 是 y ,j 是 x if(i>=y||j>=x||j<0||i<0||grid[i][j]!=1)return 0; grid[i][j]=-1; return 1+dfs(i+1,j)+dfs(i-1,j)+dfs(i,j-1)+dfs(i,j+1);

}
for(let i=0;i<y;i++){
    // i 是 y ,j 是 x 
    for(let j=0;j<x;j++){
        if(grid[i][j]){
           res=Math.max(res, dfs(i,j))
        }
    }
}
return res

};

[declan92]

java code

class Solution {
    int ans = 0;
    public int maxAreaOfIsland(int[][] grid) {
        for(int i = 0;i<grid.length;i++){
            for(int j = 0;j<grid[i].length;j++){
                if(grid[i][j]==1){
                    ans =  Math.max(dfs(grid,i,j),ans);
                }
            }
        }
        return ans;
    }

    public int dfs(int[][] grid,int i,int j){
        if(i<0||j<0||i>=grid.length || j>=grid[i].length || grid[i][j]==0 ){
            return 0;
        }
        grid[i][j]=0;
        int count = 1;
        count += dfs(grid,i+1,j);
        count += dfs(grid,i-1,j);
        count += dfs(grid,i,j+1);
        count += dfs(grid,i,j-1);
        return count;
    }
}

时间:O($mn$)
空间:O($mn$)

[zzzpppy]

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == 1){
                    res = Math.max(res, bfs(grid, i, j));
                }   
            }
        }
        return res;
    }

    public int bfs(int[][] grid, int i, int j){
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        grid[i][j] = 0;
        int area = 1;
        while(!queue.isEmpty()){
            int[] x = queue.poll();
            for(int index = 0; index < 4; index++){
                int nx = x[0] + dx[index], ny = x[1] + dy[index];
                if(nx>=0 && nx < grid.length && ny >= 0 && ny < grid[0].length && grid[nx][ny] == 1){
                    grid[nx][ny] = 0;
                    area += 1;
                    queue.offer(new int[]{nx, ny});
                }
            }
        }
        return area;
    }
}

[CodingProgrammer]

思路

回溯 + 标记：0——水，1——未访问过的陆地，-1——访问过的陆地

代码

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            throw new IllegalArgumentException();
        }

        int rows = grid.length, cols = grid[0].length;
        int areaMax = 0;
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] == 1) {
                    areaMax = Math.max(areaMax, backtracking(grid, row, col, rows, cols));
                }
            }
        }
        return areaMax;
    }
    // 0-水 1-未访问 -1-已访问
    private int backtracking(int[][] grid, int row, int col, int rows, int cols) {
        // 越界
        if (row < 0 || row >= rows || col < 0 || col >= cols) return 0;
        // 水或者已经访问过的陆地
        if (grid[row][col] != 1) return 0;
        // 当前位置已经访问，置为 -1
        grid[row][col] = -1;

        return 1 + backtracking(grid, row - 1, col, rows, cols) +
                   backtracking(grid, row + 1, col, rows, cols) +
                   backtracking(grid, row, col - 1, rows, cols) +
                   backtracking(grid, row, col + 1, rows, cols);
    }
}

复杂度

• Time: O(M*N)
• Space: O(1)

[rockydale]

// dfs const dfs = (grid, i, j) => { let m = grid.length, n = grid[0].length; if (i < 0 || j < 0 || i >= m || j >= n) { return 0; } if (grid[i][j] == 0) { return 0; } grid[i][j] = 0; return ( dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1) + 1 ); };

[L-SUI]

/**

• @param {number[][]} grid
• @return {number} */ var maxAreaOfIsland = function(grid) { const row = grid.length, col = grid[0].length let res = 0 const DFS = (i, j) => { // 下标越界返回0 if (i < 0 || i >= row || j < 0 || j >= col) { return 0 } // 值为0返回0 if(grid[i][j] == 0) {return 0} // 访问过后置为0，防止重复访问 grid[i][j] = 0 // 递归计算岛屿面积 return 1 + DFS(i, j-1) + DFS(i-1, j) + DFS(i, j+1) + DFS(i+1, j) } // 遍历二维数组 for(let i=0; i<row; i++) { for(let j=0; j<col; j++) { if (grid[i][j] == 1) { res = Math.max(res, DFS(i,j)) } else { continue } } } return res };

[GaoMinghao]

思路

感觉一般这种从一个点散开的都是用DFS会很直观，而且基本上没什么特殊的优化方法，都需要完全遍历，小trick，记录岛屿的当前大小的时候用一个一个值的数组，相当于变成了引用传递，可以避免定义一堆变量还要修改值

代码

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int ans = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] != 0) {
                    int[] currentArea = new int[1];
                    dfs(grid, i , j , currentArea); // 这样currentArea就会直接变化，不需要传参了
                    ans = Math.max(ans, currentArea[0]);
                }
            }
        }
        return ans;
    }

    void dfs(int[][] grid, int row, int col, int[] currentArea) {
        int rowMax = grid.length-1, colMax = grid[0].length-1;
        if(col < 0 || col > colMax || row < 0 ||row > rowMax || grid[row][col] == 0)
            return;
        grid[row][col] = 0;
        currentArea[0] += 1;
        dfs(grid, row, col-1,currentArea);
        dfs(grid, row, col+1,currentArea);
        dfs(grid,row-1,col,currentArea);
        dfs(grid,row+1,col,currentArea);
    }
}

[linyang4]

思路

BFS

代码(JavaScript)

var numIslands = function(grid) {
    const rows = grid.length
    if (rows === 0) { return 0 }
    const cols = grid[0].length
    if (cols === 0) { return 0 }
    let ans = 0
    for(let i = 0;i < rows; i++) {
        for(let j = 0; j < cols; j++) {
            if (grid[i][j] === '1') {
                ans++
                const queue = [{ i, j }]
                while(queue.length > 0) {
                    const { i, j } = queue.shift()
                    if (grid[i][j] === '1') {
                        grid[i][j] = '0'
                    }
                    // right
                    if (j < cols - 1 && grid[i][j + 1] === '1') {
                        queue.push({ i, j: j + 1 })
                    }
                    // bottom
                    if (i < rows - 1 && grid[i + 1][j] === '1') {
                        queue.push({ i: i + 1, j })
                    }
                    // top
                    if (i > 0 && grid[i - 1][j] === '1') {
                        queue.push({ i: i - 1, j })
                    }
                    // left
                    if (j > 0 && grid[i][j - 1] === '1') {
                        queue.push({ i, j: j - 1 })
                    }
                }
            }
        }
    }
    return ans
};

复杂度

M为grid的行数, N为grid的列数

• 时间复杂度: O(M * N)
• 空间复杂度: O(min(M, N))

[machuangmr]

代码

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                maxArea = Math.max(maxArea, dfs(grid,i,j));
            }
        }
        return maxArea;
    }
    public int dfs (int[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0) {
            return 0;
        }
        //Overwrite (i,j) as 0, mark as visited
        grid[i][j] = 0;
        return 1 + dfs(grid, i + 1, j) + dfs(grid, i, j + 1) + dfs(grid, i - 1, j) + dfs(grid, i, j - 1);
    }

}

[fornobugworld]

class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: m = len(grid) n = len(grid[0]) count = 0 def dfs(i,j): if i<0 or i>m-1 or j < 0 or j > n-1: return 0 if grid[i][j] == 0 : return 0

        grid[i][j] = 0
        return 1+dfs(i-1,j)+ dfs(i+1,j) + dfs(i,j-1) + dfs(i,j+1)

    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                count =max(count,dfs(i,j))
    return count

[spacker-343]

思路

dfs

代码

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int res=0;
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[i].length; j++){
                if(grid[i][j]==0){
                    continue;
                }
                int area=dfs(grid, i, j);
                res=Math.max(res, area);
            }
        }
        return res;
    }

    private int dfs(int[][] grid, int i, int j){
        if(i<0 || j<0 || i>=grid.length || j>=grid[0].length){
            return 0;
        }
        if(grid[i][j]==0){
            return 0;
        }
        grid[i][j]=0;
        return dfs(grid, i+1, j) +
               + dfs(grid, i-1, j)
               + dfs(grid, i, j+1)
               + dfs(grid, i, j-1)
               + 1;
    }
}

[moirobinzhang]

Code:

public class Solution {

private int[] xDirections = new int[] {1, 0, -1, 0};
private int[] yDirections = new int[] {0, 1, 0, -1};
private int maxArea = 0;
private int rowNum = 0;
private int colNum = 0;

public int MaxAreaOfIsland(int[,] grid) {
    if (grid == null || grid.GetLength(0) == 0)
        return maxArea;

    rowNum= grid.GetLength(0);
    colNum = grid.GetLength(1);

    for(int i = 0; i< rowNum; i++)
    {
        for (int j = 0; j< colNum; j++)
        {
            if (grid[i, j] == 1)
            {
                maxArea = Math.Max(maxArea, MaxAreaBFS(grid, i, j));
            }
        }
    }

    return maxArea;
}

public int MaxAreaBFS(int[,] grid, int x, int y)
{
    int area = 1;

    Queue<int> xP = new Queue<int>();
    Queue<int> yP = new Queue<int>();

    xP.Enqueue(x);
    yP.Enqueue(y);

    grid[x, y] = 0;
    int currentX = 0;
    int currentY = 0;
    int newX = 0;
    int newY = 0;

    while(xP.Count > 0)
    {
        currentX = xP.Dequeue();
        currentY = yP.Dequeue();

        for (int i = 0; i< 4; i++)
        {
            newX = currentX + xDirections[i];
            newY = currentY + yDirections[i];

            if (newX >= 0 && newX < rowNum && newY >= 0 && newY < colNum && grid[newX, newY] == 1)
            {
                xP.Enqueue(newX);
                yP.Enqueue(newY);
                grid[newX, newY] = 0;
                area++;
            }
        }

    }

    return area;

}

}

[RocJeMaintiendrai]

class Solution { boolean seen[][]; public int maxAreaOfIsland(int[][] grid) { int res = 0; int rows = grid.length; int cols = grid[0].length; seen = new boolean[rows][cols]; for(int i = 0; i < rows; i++) { for(int j = 0; j < cols; j++) { res = Math.max(res, dfs(i, j, grid)); } } return res; }

private int dfs(int row, int col, int[][] grid) {
    if(row < 0 || row >= grid.length || col < 0 || col >= grid[row].length || seen[row][col] || grid[row][col] == 0) {
        return 0;
    }

    seen[row][col] = true;
    return 1 + dfs(row + 1, col, grid) + dfs(row - 1, col, grid) + dfs(row, col + 1, grid) + dfs(row, col - 1, grid);
}

}