- 浏览: 173268 次
- 性别:
- 来自: 济南
文章分类
最新评论
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的个数即可,代码如下:
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); } } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 225Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 224You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 340Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 331Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 449Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 509Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 428Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 427The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 385Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 515Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 529Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 367All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 859Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 880Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 553Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 599Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 762Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 732You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 627For a undirected graph with tre ...
相关推荐
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) ...
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
Islands:DFS My Calendar II:小空间匹配 My Calendar I:同上 *732. My Calendar III:难,小数据量可以用线段匹配,大数据量要用LCT(但是这东西看不懂) Construct String from Binary Tree:中序遍历 Word Ladder...
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:...
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 不同岛屿的数量 给定一个由 0 和 1 组成的非空 2D 阵列网格,岛是一组 1(代表陆地)以 ...个方向(水平或垂直)连接。您可以假设网格的所有四个边缘都被水包围。...当且仅当一个岛可以平移(而不是旋转...
题目 给定一个由 ‘1’(陆地)和 ...链接:https://leetcode-cn.com/problems/number-of-islands 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 思路 用宽度优先搜索思想,将一个根节点(取
(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 ...
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) ** 给定一个由 ‘1’(陆地)和 ‘0’(水)...链接:https://leetcode-cn.com/problems/number-of-islands 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/number-of-islands 示例 1: 输入: 11110 11010 11000 00000 输出: 1 示例 2: 输入: 11000 11000 00100 00011 输出: 3 解释: 每座岛屿只能由水平和/...