这个是图像中的填充技术,即选择一个种子,然后对其周边联通的的依次填充。
代码未必最快,但很容易理解。
算法复杂度O(M*N)
空间复杂度O(M*N),最坏情况。
算法说明:
<1>初始化 访问标记
<2>对每一个没有访问的cell,进行填充算法
填充算法:(使用栈)
<1>设置初始种子,入栈
<2>如果栈空,结束
<3>出栈
依次对周围连通的cell,且没有被填充过,入栈
转2。
class Solution { public: int numIslands(vector<vector<char>> &grid) { if(grid.empty()||grid[0].empty()){ return 0; } int scc=0; const int M=grid.size(); const int N=grid[0].size(); vector<vector<int> > visited(M); for(int i=0;i<M;i++) { visited[i].resize(N); } vector<pair<int,int> > s; for(int i=0;i<M;i++) { for(int j=0;j<N;j++) { if(!visited[i][j] && grid[i][j]=='1') { s.clear(); visited[i][j]=1; s.push_back(pair<int,int>(i,j)); while(!s.empty()) { pair<int,int> pr = s.back(); s.pop_back(); int x = pr.first; int y = pr.second; x=pr.first-1; if(x>=0&&grid[x][y]=='1' && !visited[x][y]) { visited[x][y]=1; s.push_back(pair<int,int>(x,y)); } x=pr.first+1; if(x<M&&grid[x][y]=='1' && !visited[x][y]) { visited[x][y]=1; s.push_back(pair<int,int>(x,y)); } x=pr.first; y=pr.second-1; if(y>=0&&grid[x][y]=='1' && !visited[x][y]) { visited[x][y]=1; s.push_back(pair<int,int>(x,y)); } y=pr.second+1; if(y<N&&grid[x][y]=='1' && !visited[x][y]) { visited[x][y]=1; s.push_back(pair<int,int>(x,y)); } } ++scc; } } } return scc; } };
相关推荐
LeetCode上有一道经典的算法题,题目名为“Number of Islands”,即“岛屿数量”。在编程语言Java中,解决这一问题的算法通常涉及到深度优先搜索(DFS)的实现。岛屿问题本质上是使用二维数组模拟一个网格,其中“1...
针对这个问题,LeetCode上的Number of Islands II题目要求通过编写算法来解决这个问题。本篇题解将详细探讨如何使用Java语言实现这一问题的解决方案。 首先,理解问题的背景至关重要。在Number of Islands II的问题...
对于200号问题“Number of Islands”,这是一个典型的图论问题,主要考察了深度优先搜索(DFS)和广度优先搜索(BFS)算法的应用。在Python中,解决此类问题通常会使用递归或队列等数据结构。 此题目的核心是求解...
在处理给定的文件内容时,我们可以聚焦于解析"Number of Closed Islands"问题,并讨论其在Java语言中的实现。在这部分中,我们将详细介绍关于该问题的背景、概念、关键点以及Java实现的代码逻辑。 首先,"Number of...
Java LeetCode题解之Number of Big Islands是一篇针对特定编程问题的详细解决方案文章,它使用Java语言编写。该问题涉及到图论和深度优先搜索算法。在该题目中,需要识别在一个二维网格中,由“1”组成的大型岛屿的...
题目 给定一个由 ‘1’(陆地)和 ...链接:https://leetcode-cn.com/problems/number-of-islands 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 思路 用宽度优先搜索思想,将一个根节点(取
200. 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 打卡...
lru缓存leetcode 力扣_30天 力扣 30 天挑战赛 日 问题描述 问题和解决方案链接 Git 解决方案页面 1 SINGLE NUMBER 2 HAPPY NUMBER 3 MAXIMUM SUBARRAY 4 Move Zeroes 5 Best Time to Buy and Sell Stock II 6 GROUP ...
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:...
Islands:DFS My Calendar II:小空间匹配 My Calendar I:同上 *732. My Calendar III:难,小数据量可以用线段匹配,大数据量要用LCT(但是这东西看不懂) Construct String from Binary Tree:中序遍历 Word Ladder...
191 |[Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/) | [C++](./C++/number-of-1-bits.cpp) [Python](./Python/number-of-1-bits.py) | _O(1)_ | _O(1)_ | Easy ||| 201 | [Bitwise AND of ...
Number of Islands(岛屿数量),这类问题通常与图的遍历算法有关;LRU Cache(最近最少使用缓存),这需要了解缓存淘汰算法并实现相关的数据结构。 综上所述,LeetCode上的题目涵盖了计算机科学中的众多重要知识点...
狼人问题leetcode 不同岛屿的数量 给定一个由 0 和 1 组成的非空 2D 阵列网格,岛是一组 1(代表陆地)以 4 个方向(水平或垂直)连接。您可以假设网格的所有四个边缘都被水包围。 计算不同岛屿的数量。 当且仅当一...
在探讨标题“引导场对重联磁岛内磁场结构的影响:二维全粒子模拟”所含的知识点之前,首先需要理解文档中的一些专业术语和概念。 磁岛(Magnetic Island)是磁场重联过程中的一个现象,指的是在等离子体中的磁场线...
- **Number of Islands**:这个问题要求计算二维数组(可以视为网格)中连通的“1”(代表陆地)组成的岛屿数量。 - **Valid Sudoku**:检查一个数独是否有效,即每一行、每一列以及每一个宫格内的数字是否都在1到...
10. **图论**:包括深度优先搜索(DFS)和广度优先搜索(BFS),例如"岛屿数量"(Number of Islands)要求计算二维矩阵中的连通岛屿。 Python 作为一种强大且易学的语言,是解决这些问题的常用工具,其简洁的语法和...
例如,"岛屿数量"(Number of Islands)问题,找出二进制矩阵中的连通岛屿。 7. **动态规划(Dynamic Programming)**:动态规划是解决复杂问题的有效方法,通过将问题分解为子问题来求解。例如,"背包问题"...
In the Galapagos Islands, where 97% of the territory is protected and ecosystem dynamics are highly vulnerable, timely and accurate information is key for decision making. An appropriate monitoring ...
--d=200 --d=300 d=40o d=50o I I 2000 4000 60.00 sensing angle, degree I 8000 Figure 1. Return Factor vs. LiDAR Scan Angle. Figure shows relationship between water surface return and scan angle. Return...