leetcode200-岛屿数量

原题

给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例1:

输入:
11110
11010
11000
00000

输出: 1

示例2:

输入:
11000
11000
00100
00011

输出: 3

解法

思想

线性扫描整个二维网格,如果一个结点包含 1,则以其为根结点启动广度优先搜索,或深度优先搜索。搜索到的值设为 0 以标记访问过该结点,每经历过一次搜索说明岛的数量+1。直到整个二维数组都变成0。

代码

不嫌麻烦的可以建一个存储二维数组x、y位置的数据结构类。不然只能存储元素的偏移地址手动算x和y。

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        int height = grid.length;
        if(height==0) return 0;
        int width = grid[0].length;
        Queue<Integer> queue = new LinkedList<Integer>();

        for(int i = 0;i<height;i++){
            for(int j = 0;j<width;j++){
                if(grid[i][j]=='1'){
                    grid[i][j] = '0';
                    queue.offer(i*width+j);
                    while(!queue.isEmpty()){
                        int index = queue.poll();
                        int index_x = index/width;
                        int index_y = index%width;
                        if(index_x!=height-1 && grid[index_x+1][index_y]=='1'){ 
                            queue.offer((index_x+1)*width+index_y);
                            grid[index_x+1][index_y] = '0';
                        }
                        if(index_x!=0 && grid[index_x-1][index_y]=='1'){ 
                            queue.offer((index_x-1)*width+index_y);
                            grid[index_x-1][index_y] = '0';
                        }
                        if(index_y!=0 && grid[index_x][index_y-1]=='1'){ 
                            queue.offer(index_x*width+index_y-1);
                            grid[index_x][index_y-1] = '0';
                        }
                        if(index_y!=width-1 && grid[index_x][index_y+1]=='1'){ 
                            queue.offer(index_x*width+index_y+1);
                            grid[index_x][index_y+1] = '0';
                        }
                    }
                    count++;
                }
            }
        }
        return count;
    }
}

在BFS的基础上改一下就成了DFS:

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        int height = grid.length;
        if(height==0) return 0;
        int width = grid[0].length;
        Stack<Integer> stack = new Stack<>();

        for(int i = 0;i<height;i++){
            for(int j = 0;j<width;j++){
                if(grid[i][j]=='1'){
                    grid[i][j] = '0';
                    stack.push(i*width+j);
                    while(!stack.empty()){
                        int index = stack.peek();
                        int index_x = index/width;
                        int index_y = index%width;
                        if(index_x!=height-1 && grid[index_x+1][index_y]=='1'){ 
                            stack.push((index_x+1)*width+index_y);
                            grid[index_x+1][index_y] = '0';
                            continue;
                        }
                        if(index_x!=0 && grid[index_x-1][index_y]=='1'){ 
                            stack.push((index_x-1)*width+index_y);
                            grid[index_x-1][index_y] = '0';
                            continue;
                        }
                        if(index_y!=0 && grid[index_x][index_y-1]=='1'){ 
                            stack.push(index_x*width+index_y-1);
                            grid[index_x][index_y-1] = '0';
                            continue;
                        }
                        if(index_y!=width-1 && grid[index_x][index_y+1]=='1'){ 
                            stack.push(index_x*width+index_y+1);
                            grid[index_x][index_y+1] = '0';
                            continue;
                        }else{
                            stack.pop();
                        }
                    }
                    count++;
                }
            }
        }
        return count;
    }
}

当然DFS还可以用递归的系统调用栈:(作者:LeetCode)

class Solution {
  void dfs(char[][] grid, int r, int c) {
    int nr = grid.length;
    int nc = grid[0].length;

    if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
      return;
    }

    grid[r][c] = '0';
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
  }

  public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) {
      return 0;
    }

    int nr = grid.length;
    int nc = grid[0].length;
    int num_islands = 0;
    for (int r = 0; r < nr; ++r) {
      for (int c = 0; c < nc; ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          dfs(grid, r, c);
        }
      }
    }

    return num_islands;
  }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode200-%e5%b2%9b%e5%b1%bf%e6%95%b0%e9%87%8f/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年11月23日
下一篇 2019年11月25日

相关推荐

  • leetcode385-迷你语法分析器

    原题 给定一个用字符串表示的整数的嵌套列表,实现一个解析它的语法分析器。 列表中的每个元素只可能是整数或整数嵌套列表 提示: 你可以假定这些字符串都是格式良好的: 字符串非空 字符…

    算法 2020年1月28日
    02260
  • leetcode199-二叉树的右视图

    原题 给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例: 输入: [1,2,3,null,5,null,4] 输出:&nb…

    算法 2020年4月22日
    0110
  • leetcode57-插入区间

    原题 给出一个无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 输入: …

    算法 2020年5月12日
    0280
  • 剑指offer51-数组中的逆序对

    原题(来源Leetcode) 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。 示例 1: 输入: [7…

    算法 2020年4月24日
    0400
  • leetcode133-克隆图

    原题 给定无向连通图中一个节点的引用,返回该图的深拷贝(克隆)。图中的每个节点都包含它的值 val(Int) 和其邻居的列表(list[Node])。 示例: 输入: {"$id"…

    2019年12月12日
    0150
  • leetcode202-快乐数

    原题 编写一个算法来判断一个数是不是“快乐数”。 一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无…

    算法 2019年12月18日
    0120
  • leetcode80-删除排序数组中的重复项II

    原题 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外…

    算法 2020年5月26日
    0140
  • leetcode503-下一个更大元素II

    原题 给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,…

    算法 2020年2月1日
    0100
  • 使用递归函数逆序一个栈

    原题(来源:牛客网) 一个栈依次压入1,2,3,4,5那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后,从栈顶到栈底为1,2,3,4,5,也就是实现了栈中元素的逆序,请设计…

    算法 2020年4月19日
    0250
  • leetcode453-最小移动次数使数组元素相等

    原题 给定一个长度为 n 的非空整数数组,找到让数组所有元素相等的最小移动次数。每次移动将会使 n - 1 个元素增加 1。 示例: 输入: [1,2,3] 输出: 3 解释: 只…

    算法 2020年6月7日
    0140

发表回复

登录后才能评论