【LeetCode】 200. Number of Islands 岛屿数量（Medium）（JAVA）每日一题_java given an m x n 2d grid map of '1's (land) and

【LeetCode】 200. Number of Islands 岛屿数量（Medium）（JAVA）

题目地址: https://leetcode.com/problems/number-of-islands/

题目描述：

Given a 2d grid map of '1’s (land) and '0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1
1
2
3
4
5
6
7

Example 2:

Input:
11000
11000
00100
00011

Output: 3
1
2
3
4
5
6
7

题目大意

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

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

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

解题方法

遍历所有的元素，如果为 ‘1’ 不断扩张，知道遇不到 ‘1’ 为止；同时把遇到的 ‘1’ 置为 ‘0’ 防止重复遍历

class Solution {
    public int numIslands(char[][] 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] == '0') continue;
                nH(grid, i, j);
                res++;
            }
        }
        return res;
    }

    int[][] ori = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public void nH(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;
        grid[i][j] = '0';
        for (int k = 0; k < ori.length; k++) {
            nH(grid, i + ori[k][0], j + ori[k][1]);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

执行用时 : 2 ms, 在所有 Java 提交中击败了 96.16% 的用户
内存消耗 : 42.1 MB, 在所有 Java 提交中击败了 6.25% 的用户