力扣labuladong——一刷day75

本文主要是介绍力扣labuladong——一刷day75，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言
一、力扣200. 岛屿数量（广搜）
二、力扣200. 岛屿数量（深搜）

前言

图论，深搜还有广搜都只是手段

一、力扣200. 岛屿数量（广搜）

class Solution {int[][] arr = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};boolean[][] flag;public int numIslands(char[][] grid) {int count = 0;flag = new boolean[grid.length][grid[0].length];for(int i = 0; i < grid.length; i ++){for(int j = 0; j < grid[0].length; j ++){if(!flag[i][j] && grid[i][j] == '1'){count ++;bfs(grid, i, j);}}}return count;}public void bfs(char[][] grid, int x, int y){Deque<int[]> deq = new ArrayDeque<>();deq.offerLast(new int[]{x,y});flag[x][y] = true;while(!deq.isEmpty()){int size = deq.size();for(int i = 0; i < size; i ++){int[] cur = deq.pollFirst();for(int j = 0; j < 4; j ++){int curX = cur[0] + arr[j][0];int curY = cur[1] + arr[j][1];if(curX < 0 || curY < 0 || curX >= grid.length || curY >= grid[0].length || grid[curX][curY] == '0' || flag[curX][curY]){continue;}flag[curX][curY] = true;deq.offerLast(new int[]{curX,curY});}}}}
}

二、力扣200. 岛屿数量（深搜）

class Solution {int[][] arr = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};boolean[][] flag;public int numIslands(char[][] grid) {int count = 0;flag = new boolean[grid.length][grid[0].length];for(int i = 0; i < grid.length; i ++){for(int j = 0; j < grid[0].length; j ++){if(!flag[i][j] && grid[i][j] == '1'){count ++;dfs(grid, i, j);}}}return count;}public void dfs(char[][] grid, int x, int y){if(flag[x][y]){return;}flag[x][y] = true;for(int i = 0; i < 4; i ++){int curX = x + arr[i][0];int curY = y + arr[i][1];if(curX < 0 || curY < 0 || curX >= grid.length || curY >= grid[0].length || grid[curX][curY] == '0'){continue;}dfs(grid, curX, curY);}}
}