Leetcode岛屿问题汇总

Leetcode岛屿问题汇总

Leetcode岛屿问题汇总-图的遍历

leetcode中的岛屿问题，本质上是图的遍历问题，所以我们需要先了解什么事图的遍历，以及一般的遍历方法。

图的遍历

图的遍历，属于数据结构中的内容。指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。

图的遍历，分为广度优先搜索（Breadth First Search, BFS）和深度优先搜索（Depth First Search, DFS）两种。

广度优先搜索

类似于树的层次遍历。

设从V0出发

1）访问V0;

2）依次访问V0的所有邻接点V1, V2, ．．．, Vt;

3）依次访问V1的所有邻接点;

     依次访问V2的所有邻接点;

　　．．．．．．

     依次访问Vt的所有邻接点;

直到所有顶点被访问完。

注意：不能重复访问。

根据算法的描述，我们很容易就能联想到使用队列来实现BFS：

（1）每访问1个顶点后，让该顶点的序号进队;

（2）然后队头出队，将未访问过的邻接点访问后再依次进队;

         ．．．．．．

         直到队空为止;

伪代码实现：

public void BFS(Vnode[] G, int v) //对图G从序号为v的顶点出发，按BFS遍历
{   int u; qtype Q; ClearQueue(Q);   //置队Q为空visit(G,v); visited[v] = true; //访问顶点, 置标志为“已访问” EnQueue(Q, v);    //v进队while (!EmptyQueue(Q))  { //队非空时v = DeQueue(Q); //出队, 队头送vu = FirstAdj(G, v); //取v的第一邻接点序号while (u >= 0) {if (visited[u] == false) { //u未访问过visit(G, u); visited[u] = true; EnQueue(Q, u);}u = NextAdj(G, v, u);  //取v关于u的下一邻接点}}
} 

深度优先搜索

类似于树的前序遍历。

从某个顶点出发，沿着图的某个分支搜索直到头，然后回溯（Backtracking），沿着另一分支搜索。

注意：不能重复访问（图可能有回路，避免陷入死循环）

伪代码实现（递归）:

public void DFS(Vnode[] G, int v) //对图G从序号为v的顶点出发，按DFS搜索
{   int u; visit(G, v); //访问v号顶点visited[v] = true; //置标志位为”已访问”u = FirstAdj(G, v); //取v的第一邻接点序号uwhile (u >= 0) {  //当u存在时if (visited[u] == false) DFS(G, u); //递归调用遍历从u 出发的子图u = NextAdj(G, v, u); //取v关于当前u的下一邻接点序号 }
}  

除此之外，也可使用栈来实现：

public void BFS(Vnode[] G, int v) //对图G从序号为v的顶点出发，按BFS遍历
{   int u; Stack s; ClearStack(s);   //置栈s为空visit(G,v); visited[v] = true; //访问顶点, 置标志为“已访问” s.push(v);   //v进栈while (!s.isEmpty)  { //栈非空时v = s.pop(); //出栈u = FirstAdj(G, v); //取v的第一邻接点序号while (u >= 0) {if (visited[u] == false) { //u未访问过visit(G, u); visited[u] = true; s.Node());//u的兄弟节点先入栈s.push(u);//u入栈}}}
} 

leetcode中的岛屿问题，基本上都是图深度优先搜索的应用。

Leetcode岛屿问题汇总

200.岛屿数量

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

示例 1:

输入:

11110
11010
11000
00000

输出: 1

       示例 2:

输入:

11000
11000
00100
00011

输出: 3

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

对于每一个为陆地的岛屿，进行深度遍历，将所有与其联通的陆地全部访问。代码如下：

class Solution {public int numIslands(char[][] grid) {int res=0;for(int i=0;i<grid.length;i++){for(int j=0;j<grid[0].length;j++){if(grid[i][j]=='1'){//g[i][j]=0;res++;deep(grid,i,j);}}}return res;}public void deep(char[][] g,int i,int j){if(i>=0 && i<g.length && j>=0 && j<g[0].length && g[i][j]=='1'){g[i][j]='0';deep(g,i+1,j);deep(g,i-1,j);deep(g,i,j+1);deep(g,i,j-1);}}}

695.岛屿的最大面积

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]

对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2:

[[0,0,0,0,0,0,0,0]]

对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码解决：

class Solution {public int maxAreaOfIsland(int[][] grid) {int max=0;for(int i=0;i<grid.length;i++){for(int j=0;j<grid[0].length;j++){if(grid[i][j]==1){//g[i][j]=0;int temp=0;temp+=deep(grid,i,j);max=Math.max(temp,max);}}}return max;}public int deep(int[][] g,int i,int j){if(i>=0 && i<g.length && j>=0 && j<g[0].length && g[i][j]==1){g[i][j]=0;int x=1+deep(g,i+1,j)+deep(g,i-1,j)+deep(g,i,j+1)+deep(g,i,j-1);return x;}else {return 0;}}
}