`

Number of Islands

阅读更多
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:

11110
11010
11000
00000
Answer: 1

Example 2:

11000
11000
00100
00011
Answer: 3

这道题的意思给定一个二维数组,里面只包含两个数 0和1,0代表水,1代表陆地,在水平方向和竖直方向相连的1才能代表一块连通的陆地,我们从给出的example中可以看到斜方向上的1不代表相连的陆地。
与其说这是二维数组的题目不如说是图的题目,相当于在一个图中求解包含1的连通子图。我们可以采用深度优先搜索来解决,当我们搜索到1时就把能够和它相连的所有的1都变为‘X’(可以变为任意一个不为1的字符),这样我们只需要得到遍历中1的个数即可,代码如下:
public class Solution {
    public int numIslands(char[][] grid) {
        if(grid == null || grid.length == 0) return 0;
        int m = grid.length;
        int n = grid[0].length;
        int result = 0;
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++) {
                if(grid[i][j] != '1') continue;
                result ++;
                getResult(grid, i, j);
            }
        return result;
    }
    
    public void getResult(char[][] grid, int i, int j) {
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) return;
        if(grid[i][j] == '1') {
            grid[i][j] = 'X';
            getResult(grid, i - 1, j);
            getResult(grid, i + 1, j);
            getResult(grid, i, j - 1);
            getResult(grid, i, j + 1);
        }
    }
}
分享到:
评论

相关推荐

    LeetCode最全代码

    The number of questions is increasing recently. Here is the classification of all `468` questions. For more questions and solutions, you can see my [LintCode](https://github.com/kamyu104/LintCode) ...

    lrucacheleetcode-LeetCode_30Day:力扣30天挑战赛

    lru缓存leetcode 力扣_30天 力扣 30 天挑战赛 日 问题描述 问题和解决方案链接 Git 解决方案页面 1 SINGLE NUMBER 2 HAPPY NUMBER 3 MAXIMUM SUBARRAY 4 Move Zeroes ...of ...of ...of ...Number of Islands 18 M

    leetcode316-LeetCode:leetcode的解决方案

    Islands:DFS My Calendar II:小空间匹配 My Calendar I:同上 *732. My Calendar III:难,小数据量可以用线段匹配,大数据量要用LCT(但是这东西看不懂) Construct String from Binary Tree:中序遍历 Word Ladder...

    扩展矩阵leetcode-leetcode:leetcode

    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. Input:...

    leetcode卡-LeetCode:我的LeetCode解决方案

    Number of Islands], BFS 2017.06.14 打卡[LeetCode 3. Longest Substring Without Repeating Characters], N/A 2017.06.15 打卡[LeetCode 407. Trapping Rain Water II], BFS/Priority queue 2017.06.19 打卡...

    陆地岛屿问题leetcode-number-of-distinct-islands:计算不同岛屿的数量

    狼人问题leetcode 不同岛屿的数量 给定一个由 0 和 1 组成的非空 2D 阵列网格,岛是一组 1(代表陆地)以 ...个方向(水平或垂直)连接。您可以假设网格的所有四个边缘都被水包围。...当且仅当一个岛可以平移(而不是旋转...

    LeetCode解题心得——岛屿数量(python)

    题目 给定一个由 ‘1’(陆地)和 ...链接:https://leetcode-cn.com/problems/number-of-islands 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 思路 用宽度优先搜索思想,将一个根节点(取

    spssw-184.zip

    (11.7 million sq mi) including adjacent islands, it covers 6% of the Earth's total surface area and 20.4% of the total land area.[2] With 1.0 billion people (as of 2009, see table) in 65 territories ...

    雷达技术知识

    and the Graduate School of the University of Oregon in partial fulfillment of the requirements for the degree of Master of Science March 2009 11 "Effectiveness of Extracting Water Surface Slopes from ...

    JavaScript 圣经第5版-Javascript编程宝典--黄金版 .rar

    Chapter 35: The Math, Number, and Boolean Objects. Chapter 36: The Date Object. Chapter 37: The Array Object. Chapter 38: The Regular Expression and RegExp Objects. Chapter 39: Control Structures ...

    列表实现岛屿数量(DFS+BFS)

    ** 列表实现岛屿数量(DFS+BFS) ** 给定一个由 ‘1’(陆地)和 ‘0’(水)...链接:https://leetcode-cn.com/problems/number-of-islands 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    Leetcode200. 岛屿数量

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/number-of-islands 示例 1: 输入: 11110 11010 11000 00000 输出: 1 示例 2: 输入: 11000 11000 00100 00011 输出: 3 解释: 每座岛屿只能由水平和/...

Global site tag (gtag.js) - Google Analytics