建设网站需要多少时间,电商网站运营怎么做,昆山市建设工程质量检测中心网站,十大软件管理系统题目链接
leetcode在线oj题——岛屿数量
题目描述
给你一个由 ‘1’#xff08;陆地#xff09;和 ‘0’#xff08;水#xff09;组成的的二维网格#xff0c;请你计算网格中岛屿的数量。
岛屿总是被水包围#xff0c;并且每座岛屿只能由水平方向和/或竖直方向上相…题目链接
leetcode在线oj题——岛屿数量
题目描述
给你一个由 ‘1’陆地和 ‘0’水组成的的二维网格请你计算网格中岛屿的数量。
岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外你可以假设该网格的四条边均被水包围。
题目示例
输入grid [ [“1”,“1”,“1”,“1”,“0”], [“1”,“1”,“0”,“1”,“0”], [“1”,“1”,“0”,“0”,“0”], [“0”,“0”,“0”,“0”,“0”] ] 输出1
输入grid [ [“1”,“1”,“0”,“0”,“0”], [“1”,“1”,“0”,“0”,“0”], [“0”,“0”,“1”,“0”,“0”], [“0”,“0”,“0”,“1”,“1”] ] 输出3
题目提示
m grid.lengthn grid[i].length1 m, n 300grid[i][j] 的值为 ‘0’ 或 ‘1’
解题思路
定义一个isUsed数组记录遍历过的位置
使用深度优先搜索将与一个位置连接的所有“1”都记录为以遍历最后统计总数即可
定义一个DFS方法参数分别是grid数组行数列数当前所在行当前所在列isUsed数组
将当前的位置的isUsed数组位置更新为已遍历并且分别遍历其上下左右四个位置如果没有越界并且还是“1”那么继续递归其他位置
代码
class Solution {int[][] nextPosition {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};void DFS(char[][] grid, int row, int col, int curX, int curY, boolean[][] isUsed){isUsed[curX][curY] true;//确定下一个位置for (int i 0; i 4; i) {int newX curX nextPosition[i][0];int newY curY nextPosition[i][1];//判断是否越界if(newX row || newX 0 || newY col || newY 0){continue;}if(grid[newX][newY] 1 !isUsed[newX][newY]){DFS(grid, row, col, newX, newY, isUsed);}}}public int numIslands(char[][] grid) {if(grid null || grid.length 0){return 0;}int row grid.length;int col grid[0].length;boolean[][] isUsed new boolean[row][col];int num 0;for (int i 0; i row; i) {for (int j 0; j col; j) {if(grid[i][j] 1 !isUsed[i][j]){num;DFS(grid, row, col, i, j, isUsed);}}}return num;}
}
