思路是分治法——遍历grid[][]找到一个岛屿后count然后把这个岛屿填成海洋并把相连的岛屿都填成海洋。搜索相邻的岛屿这一块可以用深度优先去实现也可以用广度优先搜索去实现。法一分治法BFS深度优先搜索的思想采用递归的手段实现↓既然是递归画图然后写递推公式主方法里i指针从上往下遍历j指针从左往右遍历所以访问到节点grid[i][j]的时候节点grid[i][j]的左边和上边都已经被访问过了所以只需要看右边和下边两个方向了对吗错错错因为我们是递归访问的上下左右四个方向都要看。比如下面这个例子就是要往左访问才能找全。既然定下来了四个方向那就是四个子节点也就是并列写4个dfs。递归出口依然采用第n1轮/先污染后治理的方式3种情况1第n1轮进来发现是海洋2第n1轮进来发现已经遍历过了。3第n1轮进来发现越界了只不过这个题比较巧我们正好用海洋标记遍历过了所以情况1和情况2可以合并。↓递归的参数写着写着就出来了就三个参数class Solution { public int numIslands(char[][] grid) { int count0; for(int i0; igrid.length; i){ for (int j0; jgrid[0].length; j){ if(grid[i][j]1){ count; dfs(grid,i,j); } } } return count; } private void dfs(char[][] grid,int i,int j){ //递归出口1:超出边界 if(i0||j0||igrid.length||jgrid[0].length) return; //递归出口2:海洋或者已经遍历过 if(grid[i][j]0) return; //根节点先处理 if(grid[i][j]1) grid[i][j]0; //陆地变海洋 //再进入子节点 dfs(grid,i-1,j); dfs(grid,i,j-1); dfs(grid,i1,j); dfs(grid,i,j1); } }法二分治法DFS只需要记住Deque ArrayDeque这个实现类既可以当队用也可以当栈用。并且当队用的时候看队首的方法是peek当栈用的时候看栈顶的方法也是peek//------------------队------------------ DequeInteger queue new ArrayDeque(); queue.offer(1); // 入队 int head queue.peek(); // 看队头不出队 int poll queue.poll(); // 出队 boolean empty queue.isEmpty(); //------------------栈------------------ DequeInteger stack new ArrayDeque(); queue.push(1); int peek stack.peek(); int pop stack.pop(); //-----------------双端队列------------------ offerFirst()、offerLast() pollFirst()、pollLast()class Solution { // 上下左右四个移动方向 private static int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public int numIslands(char[][] grid) { int count0; for(int i0; igrid.length; i){ for (int j0; jgrid[0].length; j){ if(grid[i][j]1){ count; grid[i][j]0; //BFS“根节点”的填海可以放在这里,但是dfs不行 bfs(grid,i,j); } } } return count; } private void bfs(char[][] grid,int i,int j){ Dequeint[] queue new ArrayDeque(); queue.offer(new int[]{i,j}); while(!queue.isEmpty()){ int[] poll queue.poll(); for(int m0;m4;m){ int newI poll[0]dirs[m][0]; int newJ poll[1]dirs[m][1]; //dfs只能在入队之前判断,相当于BFS在第n轮判断跟我们BFS在第n1轮判断不同 if(newI0newJ0newIgrid.lengthnewJgrid[0].length){ if(grid[newI][newJ]1){ grid[newI][newJ]0; queue.offer(new int[]{newI,newJ}); } } } } } } 
长河君 · 2026/10/10 5:47:06 · 阅读 1.2k Leetcode hot100 岛屿数量【中等】
思路是分治法——遍历grid[][]找到一个岛屿后count然后把这个岛屿填成海洋并把相连的岛屿都填成海洋。搜索相邻的岛屿这一块可以用深度优先去实现也可以用广度优先搜索去实现。法一分治法BFS深度优先搜索的思想采用递归的手段实现↓既然是递归画图然后写递推公式主方法里i指针从上往下遍历j指针从左往右遍历所以访问到节点grid[i][j]的时候节点grid[i][j]的左边和上边都已经被访问过了所以只需要看右边和下边两个方向了对吗错错错因为我们是递归访问的上下左右四个方向都要看。比如下面这个例子就是要往左访问才能找全。既然定下来了四个方向那就是四个子节点也就是并列写4个dfs。递归出口依然采用第n1轮/先污染后治理的方式3种情况1第n1轮进来发现是海洋2第n1轮进来发现已经遍历过了。3第n1轮进来发现越界了只不过这个题比较巧我们正好用海洋标记遍历过了所以情况1和情况2可以合并。↓递归的参数写着写着就出来了就三个参数class Solution { public int numIslands(char[][] grid) { int count0; for(int i0; igrid.length; i){ for (int j0; jgrid[0].length; j){ if(grid[i][j]1){ count; dfs(grid,i,j); } } } return count; } private void dfs(char[][] grid,int i,int j){ //递归出口1:超出边界 if(i0||j0||igrid.length||jgrid[0].length) return; //递归出口2:海洋或者已经遍历过 if(grid[i][j]0) return; //根节点先处理 if(grid[i][j]1) grid[i][j]0; //陆地变海洋 //再进入子节点 dfs(grid,i-1,j); dfs(grid,i,j-1); dfs(grid,i1,j); dfs(grid,i,j1); } }法二分治法DFS只需要记住Deque ArrayDeque这个实现类既可以当队用也可以当栈用。并且当队用的时候看队首的方法是peek当栈用的时候看栈顶的方法也是peek//------------------队------------------ DequeInteger queue new ArrayDeque(); queue.offer(1); // 入队 int head queue.peek(); // 看队头不出队 int poll queue.poll(); // 出队 boolean empty queue.isEmpty(); //------------------栈------------------ DequeInteger stack new ArrayDeque(); queue.push(1); int peek stack.peek(); int pop stack.pop(); //-----------------双端队列------------------ offerFirst()、offerLast() pollFirst()、pollLast()class Solution { // 上下左右四个移动方向 private static int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public int numIslands(char[][] grid) { int count0; for(int i0; igrid.length; i){ for (int j0; jgrid[0].length; j){ if(grid[i][j]1){ count; grid[i][j]0; //BFS“根节点”的填海可以放在这里,但是dfs不行 bfs(grid,i,j); } } } return count; } private void bfs(char[][] grid,int i,int j){ Dequeint[] queue new ArrayDeque(); queue.offer(new int[]{i,j}); while(!queue.isEmpty()){ int[] poll queue.poll(); for(int m0;m4;m){ int newI poll[0]dirs[m][0]; int newJ poll[1]dirs[m][1]; //dfs只能在入队之前判断,相当于BFS在第n轮判断跟我们BFS在第n1轮判断不同 if(newI0newJ0newIgrid.lengthnewJgrid[0].length){ if(grid[newI][newJ]1){ grid[newI][newJ]0; queue.offer(new int[]{newI,newJ}); } } } } } }