- 浏览: 173188 次
- 性别:
- 来自: 济南
文章分类
最新评论
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’,计数器加1,并且通过DFS从当前点开始,对和当前点连通的‘1’进行标记,然后继续搜索数组,直到结束。代码如下:
Example 1:
11110
11010
11000
00000
Answer: 1
Example 2:
11000
11000
00100
00011
Answer: 3
遍历字符数组,如果遇到‘1’,计数器加1,并且通过DFS从当前点开始,对和当前点连通的‘1’进行标记,然后继续搜索数组,直到结束。代码如下:
public class Solution { public int numIslands(char[][] grid) { if(grid == null || grid.length == 0) return 0; int result = 0; for(int i = 0; i < grid.length; i++) { for(int j = 0; j < grid[0].length; j++) { if(grid[i][j] != '1') continue; result ++; expandIsland(i, j, grid); } } return result; } public void expandIsland(int i, int j, char[][] grid) { if(i < 0 || j < 0 || i == grid.length || j == grid[0].length) return; if(grid[i][j] == '1') { grid[i][j] = 'X'; expandIsland(i - 1, j, grid); expandIsland(i + 1, j, grid); expandIsland(i, j + 1, grid); expandIsland(i, j - 1, grid); } } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 224Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 222You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 339Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 330Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 448Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 427Given 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 426The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 383Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 514Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 528Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 366All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 879Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 552Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 598Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 761Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 731You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 626For 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 解释: 每座岛屿只能由水平和/...