LeetCode刷题：200. Number of Islands

本文主要是介绍LeetCode刷题：200. Number of Islands，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeetCode刷题：200. Number of Islands

原题链接：https://leetcode.com/problems/number-of-islands/description/

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

这个题目的大概意思是给定了一个二维数组表示的地图，其中 1 代表岛，而 0 代表水，要求计算地图中岛的数量。
判断岛的规则是：岛是被水包围着，由水平或垂直相连的相邻陆地形成。
你可以假设网格的所有四个边都被水包围着。

问题分析

根据题目的描述，如图所示，岛由水包围着，由水平或垂直相连的相邻陆地形成。则图中，岛的数量为3个。

这个有很多种求解方法，其中可以使用DFS算法求解。

算法设计

package com.bean.algorithmbasic;public class NumberOfIslands2 {int y;          // 行int x;          // 列char[][] g;     // 目标数组/*** 求岛的数量*/public int numIslands(char[][] grid) {// Store the given grid// This prevents having to make copies during recursiong = grid;// 存储计算结果int ANSWER = 0;// 计算二维数组的行数y = g.length;//如果行数为0，则返回if (y == 0) return 0;//计算二维数组的列数x = g[0].length;// 对给定的二维数组单元格进行遍历访问for (int i = 0; i < y; i++) {for (int j = 0; j < x; j++) {//当某一个单元格数值为1时，调用dfs算法进行搜索if (g[i][j] == '1') {//调用DFS搜索算法dfs(i, j);//更新ANSWERANSWER++;}}}return ANSWER;}/*** DFS搜索算法* 参数代表需要访问检查的坐标位置。* 将遍历访问过的单元格标记为0*/private void dfs(int i, int j) {// 设置边界条件:如果行数<0 或者达到边界；如果列数<0 或者达到边界；或者单元格的值不是1，则返回。if (i < 0 || i >= y || j < 0 || j >= x || g[i][j] != '1') return;// 将遍历访问过的单元格标记为0g[i][j] = '0';// 检查所有相邻的位置，由上、下、左、右四个方向dfs(i + 1, j); dfs(i - 1, j);dfs(i, j + 1);dfs(i, j - 1);}public static void main(String[] args) {// TODO Auto-generated method stubchar[][]  array= {{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}};NumberOfIslands2 noi=new NumberOfIslands2();int result=noi.numIslands(array);System.out.println("RESULT IS: "+result);}}

（完）

这篇关于LeetCode刷题：200. Number of Islands的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---