【leetcode】200. (Medium)Number of Islands
解题思路:
DFS
提交代码:
class Solution {
public int numIslands(char[][] grid) {
if(grid==null||grid.length==0) return 0;
int[][] tmp=new int[grid.length][grid[0].length];
int cnt=0;
for(int i=0;i<grid.length;i++) {
for(int j=0;j<grid[0].length;j++) {
if(grid[i][j]=='1')
cnt+=check(i,j,grid,tmp);
}
}
return cnt;
}
public int check(int row,int col,char[][] grid,int[][] tmp) {
if(tmp[row][col]==1) return 0;
tmp[row][col]=1;
findRemain(row,col,grid,tmp);
return 1;
}
public void findRemain(int row,int col,char[][] grid,int[][] tmp) {
if(row!=0) {
if(grid[row-1][col]=='1'&&tmp[row-1][col]==0) {
tmp[row-1][col]=1;
findRemain(row-1,col,grid,tmp);
}
}
if(col!=0) {
if(grid[row][col-1]=='1'&&tmp[row][col-1]==0) {
tmp[row][col-1]=1;
findRemain(row,col-1,grid,tmp);
}
}
if(row!=grid.length-1) {
if(grid[row+1][col]=='1'&&tmp[row+1][col]==0) {
tmp[row+1][col]=1;
findRemain(row+1,col,grid,tmp);
}
}
if(col!=grid[0].length-1) {
if(grid[row][col+1]=='1'&&tmp[row][col+1]==0) {
tmp[row][col+1]=1;
findRemain(row,col+1,grid,tmp);
}
}
}
}
check函数用于检查当前陆地部分是否已经属于一个已知的岛屿,如果当前陆地不属于一个已知的岛屿,则将当前陆地标记为一个新的岛屿,并用findRemain函数找到和当前陆地连接起来的部分。
运行结果:
可以进一步简化为:
class Solution {
public int numIslands(char[][] grid) {
if(grid==null||grid.length==0) return 0;
int[][] tmp=new int[grid.length][grid[0].length];
int cnt=0;
for(int i=0;i<grid.length;i++) {
for(int j=0;j<grid[0].length;j++) {
if(grid[i][j]=='1'&&tmp[i][j]!=1)
cnt+=findRemain(i,j,grid,tmp);
}
}
return cnt;
}
public int findRemain(int row,int col,char[][] grid,int[][] tmp) {
tmp[row][col]=1;
if(row!=0) {
if(grid[row-1][col]=='1'&&tmp[row-1][col]==0) {
tmp[row-1][col]=1;
findRemain(row-1,col,grid,tmp);
}
}
if(col!=0) {
if(grid[row][col-1]=='1'&&tmp[row][col-1]==0) {
tmp[row][col-1]=1;
findRemain(row,col-1,grid,tmp);
}
}
if(row!=grid.length-1) {
if(grid[row+1][col]=='1'&&tmp[row+1][col]==0) {
tmp[row+1][col]=1;
findRemain(row+1,col,grid,tmp);
}
}
if(col!=grid[0].length-1) {
if(grid[row][col+1]=='1'&&tmp[row][col+1]==0) {
tmp[row][col+1]=1;
findRemain(row,col+1,grid,tmp);
}
}
return 1;
}
}
看完题目评论区的答案,发现有些可以优化的地方:
1.不使用“check”“findRemain”这种函数名,既然是利用递归的算法,可以使用DFS作为子函数名;
2.findRemain中我分别探讨了上下左右的位置情况,这样代码写起来比较复杂,可以在findRemain开始的地方设置边界返回:
if(row<0||row==grid.length||col<0||col>grid[0].length) return;
最终简化之后:
class Solution {
public int numIslands(char[][] grid) {
if(grid==null||grid.length==0) return 0;
int[][] tmp=new int[grid.length][grid[0].length];
int cnt=0;
for(int i=0;i<grid.length;i++)
for(int j=0;j<grid[0].length;j++)
if(grid[i][j]=='1'&&tmp[i][j]!=1)
cnt+=DFS(i,j,grid,tmp);
return cnt;
}
public int DFS(int row,int col,char[][] grid,int[][] tmp) {
if(row<0||col<0||row==grid.length||col==grid[0].length) return 0;
if(grid[row][col]=='0'||tmp[row][col]==1) return 0;
tmp[row][col]=1;
DFS(row-1,col,grid,tmp);
DFS(row,col-1,grid,tmp);
DFS(row+1,col,grid,tmp);
DFS(row,col+1,grid,tmp);
return 1;
}
}
运行结果: