岛屿

岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

输入:
11110
11010
11000
00000
输出: 1

示例 2:

输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成

方法一：DFS

public int numIslands(char[][] grid) {
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (dfs(grid, i, j)) {
                count++;
            }
        }
    }
    return count;
}

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

时间复杂度O(mn)
空间复杂度O(mn)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到mn

方法二：BFS

public int numIslands(char[][] grid) {
    int count = 0;
    Queue<int[]> queue = new LinkedList<>();
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                grid[i][j] = '0';
                queue.offer(new int[]{i, j});
                bfs(grid, queue);
                count++;
            }
        }
    }
    return count;
}

public void bfs(char[][] grid, Queue<int[]> queue) {
    while (!queue.isEmpty()) {
        int[] pos = queue.poll();
        int i = pos[0];
        int j = pos[1];
        if (i - 1 >= 0 && grid[i - 1][j] == '1') {
            grid[i - 1][j] = '0';
            queue.offer(new int[]{i - 1, j});
        }
        if (i + 1 < grid.length && grid[i + 1][j] == '1') {
            grid[i + 1][j] = '0';
            queue.offer(new int[]{i + 1, j});
        }
        if (j - 1 >= 0 && grid[i][j - 1] == '1') {
            grid[i][j - 1] = '0';
            queue.offer(new int[]{i, j - 1});
        }
        if (j + 1 < grid[0].length && grid[i][j + 1] == '1') {
            grid[i][j + 1] = '0';
            queue.offer(new int[]{i, j + 1});
        }
    }
}

时间复杂度O(mn)
时间复杂度O(mn)

岛屿的最大面积

给定一个包含了一些 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

方法一：DFS

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 || i >= grid.length || j < 0 ||
        j >= grid[0].length || grid[i][j] == 0) {
        return 0;
    }
    int ans = 1;
    grid[i][j] = 0;
    ans += dfs(grid, i - 1, j);
    ans += dfs(grid, i + 1, j);
    ans += dfs(grid, i, j - 1);
    ans += dfs(grid, i, j + 1);
    return ans;
}

方法二： BFS

public int maxAreaOfIsland(int[][] grid) {
    int maxArea = 0;
    Queue<int[]> queue = new LinkedList<>();
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 1) {
                grid[i][j] = 0;
                queue.offer(new int[]{i, j});
                maxArea = Math.max(maxArea, bfs(grid, queue));
            }
        }
    }
    return maxArea;
}

public int bfs(int[][] grid, Queue<int[]> queue) {
    int area = 0;
    while (!queue.isEmpty()) {
        int[] pos = queue.poll();
        int i = pos[0];
        int j = pos[1];
        area++;
        if (i - 1 >= 0 && grid[i - 1][j] == 1) {
            grid[i - 1][j] = 0;
            queue.offer(new int[]{i - 1, j});
        }
        if (i + 1 < grid.length && grid[i + 1][j] == 1) {
            grid[i + 1][j] = 0;
            queue.offer(new int[]{i + 1, j});
        }
        if (j - 1 >= 0 && grid[i][j - 1] == 1) {
            grid[i][j - 1] = 0;
            queue.offer(new int[]{i, j - 1});
        }
        if (j + 1 < grid[0].length && grid[i][j + 1] == 1) {
            grid[i][j + 1] = 0;
            queue.offer(new int[]{i, j + 1});
        }
    }
    return area;
}

岛屿的周长

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

对于一个陆地格子的每条边，它被算作岛屿的周长当且仅当这条边为网格的边界或者相邻的另一个格子为水域

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

private 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 1;
    }
    if (grid[i][j] == 2) {
        return 0;
    }
    grid[i][j] = 2;
    int res = 0;
    res += dfs(grid, i + 1, j);
    res += dfs(grid, i - 1, j);
    res += dfs(grid, i, j + 1);
    res += dfs(grid, i, j - 1);
    return res;
}

最大正方形

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4

方法一：暴力

public int maximalSquare(char[][] matrix) {
    if (matrix == null || matrix.length == 0) {
        return 0;
    }
    int maxLen = 0;
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == '1') {
                int curMaxSide = Math.min(matrix.length - i, matrix[0].length - j);//当前可能的最大边长
                int k;
                Side:
                for (k = 1; k < curMaxSide; k++) {
                    if (matrix[i + k][j + k] == '1') {//对角线为1
                        for (int m = 0; m < k; m++) {//新增的一行一列是否都为1
                            if (matrix[i + k][m + j] == '0' || matrix[i + m][j + k] == '0') {
                                break Side;
                            }
                        }
                    } else {
                        break;
                    }
                }
                maxLen = Math.max(maxLen, k);
            }
        }
    }
    return maxLen * maxLen;
}

时间复杂度O(mn min(m,n)2)

方法二：动态规划
dp(i, j)表示以 (i, j)为右下角，且只包含 1 的正方形的边长最大值

如果该位置的值是 0，则 dp(i, j) = 0

如果该位置的值是 1，则 dp(i, j)的值由其上方、左方和左上方的三个相邻位置的 dp 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1，状态转移方程如下：

dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1

此外，还需要考虑边界条件。如果 i 和 j中至少有一个为 0，则以位置 (i, j) 为右下角的最大正方形的边长只能是 1，因此 dp(i, j) = 1

public int maximalSquare(char[][] matrix) { 
    if (matrix == null || matrix.length == 0) {
        return 0;
    }
    int maxLen = 0;
    int[][] dp = new int[matrix.length][matrix[0].length];
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == '1' ){
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j -1]), dp[i -1][j]) + 1;
                }
                maxLen = Math.max(maxLen, dp[i][j]);
            }
        }
    }
    return maxLen * maxLen;
}

时间复杂度O(mn)

方法三：二进制思路（未通过）
把矩阵中的每一行看做二进制数

例子：
1 0 1 0 0
1 0 1 1 1
两数相与得到
1 0 1 0 0
在这个数字中，连续的 1 就可以看作是正方形的宽，而高度就是 2，因为是 2 个数相与的。所以能构成的最大正方形边长为 min(宽,高)=min(1,2)=1。

  • 用 2 个指针 i,j 分别表示开始行和最后一行，这2行之间的所有行（包括这 2 行）全部相与，看能得到多少个连续最多的 1，亦即求宽度，而高度则等于 j-i+1。枚举所有的(i,j) 组合，并保存结果中的最大值。
  • 如何求一个数中连续最多的 1？小技巧：每次将这个数和它左移一位后的数相与，直到它变成 0，记录操作次数，这个操作次数就是连续最多的 1

由于可能列很长，转换成long型的数失败，所以不能通过

public int maximalSquare(char[][] matrix) {
    if (matrix == null || matrix.length == 0) {
        return 0;
    }
    int maxLen = 0;
    long[] nums = new long[matrix.length];
    //转成二进制数
    for (int i = 0; i < nums.length; i++) {
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < matrix[0].length; j++) {
            sb.append(matrix[i][j]);
        }
        nums[i] += Long.valueOf(sb.toString(), 2);
    }
    for (int i = 0; i < nums.length; i++) {
        if (maxLen >= matrix.length - i) { //不可能有更长的边了
            break;
        }
        long temp = nums[i];
        for (int j = i; j < nums.length; j++) {
            temp &= nums[j];
            int width = getWidth(temp);
            maxLen = Math.max(maxLen, Math.min(width, j - i + 1));
        }
    }
    return maxLen * maxLen;
}

public int getWidth(long num) {
    int width = 0;
    while (num != 0) {
        num = num & num >>> 1;
        width++;
    }
    return width;
}

统计全为 1 的正方形子矩阵

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

示例 1：

输入：matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
输出：15

解释：
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

示例 2：

输入：matrix =
[
[1,0,1],
[1,1,0],
[1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7

方法一：暴力

public int countSquares(int[][] matrix) {
    if (matrix == null || matrix.length == 0) {
        return 0;
    }
    int ans = 0;
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == 1) {
                ans++;
                int curMaxSide = Math.min(matrix.length - i, matrix[0].length - j);//当前可能的最大边长
                int k;
                Side:
                for (k = 1; k < curMaxSide; k++) {
                    if (matrix[i + k][j + k] == 1) {//对角线为1
                        for (int m = 0; m < k; m++) {//新增的一行一列是否都为1
                            if (matrix[i + k][m + j] == 0 || matrix[i + m][j + k] == 0) {
                                break Side;
                            }
                        }
                    } else {
                        break;
                    }
                    ans++;
                }
            }
        }
    }
    return ans;
}

方法二：动态规划

public int countSquares(int[][] matrix) {
    if (matrix == null || matrix.length == 0) {
        return 0;
    }
    int ans = 0;
    int[][] dp = new int[matrix.length][matrix[0].length];
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == 1) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j -1]), dp[i -1][j]) + 1;
                }
                ans += dp[i][j];
            }
        }
    }
    return ans;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

友情链接更多精彩内容