leetcode打卡-深度优先遍历和广度优先遍历

200.岛屿数量

leetcode题目链接：https://leetcode.cn/problems/number-of-islands

leetcode AC记录：

思路：深度优先遍历，从0，0开始遍历数组，使用boolean类型数组used记录是否被访问过，进行一次完整的深度优先遍历后，岛屿数量加1，也就是所有和当前1联通的位置认为是同一岛屿。

代码如下：

 public int numIslands(char[][] grid) {int res = 0;boolean[][] used = 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(grid[i][j] == '1' && !used[i][j]) {res++;dfs(grid.length, grid[0].length, i, j, grid, used);}}}return res;}public void dfs(int xlength, int ylength, int x,int y, char[][] grid, boolean[][] used) {if(x >= 0 && y >= 0 && x < xlength && y < ylength && !used[x][y] && grid[x][y] == '1') {used[x][y] = true;dfs(xlength, ylength, x-1, y, grid, used);dfs(xlength, ylength, x, y-1, grid, used);dfs(xlength, ylength, x+1, y, grid, used);dfs(xlength, ylength, x, y+1, grid, used);}}

130. 被围绕的区域

leetcode题目链接：https://leetcode.cn/problems/surrounded-regions

leetcode AC记录：

思路：如果直接使用深度优先遍历并记录是否触碰到边缘会有问题。所以从边缘开始处理，遇到边缘，判断条件如下代码。处理步骤是判断边缘，如果符合并且没有被访问过，进行深度优先遍历，把遍历节点替换为@。深度优先遍历结束后，再次遍历数组，如果是@，替换回O，如果是O，说明是符合条件的，替换为X。

代码如下：

public void solve(char[][] board) {int xLength = board.length, yLength = board[0].length;boolean[][] used = new boolean[xLength][yLength];for(int i = 0;i < xLength;i++) {for(int j = 0;j < yLength;j++) {if(isEdge(i, j, xLength, yLength) && !used[i][j]) {dfs(board, i,j, used);}}}for(int i = 0;i < xLength;i++) {for(int j = 0;j < yLength;j++) {if(board[i][j] == 'O') {board[i][j] = 'X';} else if(board[i][j] == '@') {board[i][j] = 'O';}}}}public boolean isEdge(int x, int y, int xLength, int yLength) {return (x == 0 || y == 0 || x == xLength -1 || y == yLength -1);}public void dfs(char[][] board, int x, int y, boolean[][] used) {if(x >= 0 && y >= 0 && x < board.length && y < board[0].length) {if(!used[x][y] && board[x][y] == 'O') {used[x][y] = true;board[x][y] = '@';dfs(board, x-1, y, used);dfs(board, x, y-1, used);dfs(board, x, y+1, used);dfs(board, x+1, y, used);}}}

1091. 二进制矩阵中的最短路径

leetcode题目链接：https://leetcode.cn/problems/shortest-path-in-binary-matrix

leetcode AC记录：

思路：广度优先遍历，结果就是遍历的层数，最小值靠优先返回保证。首先将0，0入队，队列不为空进行循环，遍历每一层，也就是当前队列大小（得用变量临时保存，不然队列的大小会随着入队操作变化）。然后出队，取出相临的节点，判断如果值符合数组下标并且值是0，放入队列中，如果当前取出的是数组右下脚的值，则返回结果。

 代码如下：

 public int shortestPathBinaryMatrix(int[][] grid) {Deque<Point> queue = new LinkedList<>();queue.offer(new Point(0,0));boolean[][] used = new boolean[grid.length][grid[0].length];int res = 1;while(!queue.isEmpty()) {int size = queue.size();for(int i = 0;i < size;i++) {Point point = queue.poll();int x = point.x, y = point.y;if(x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && grid[x][y] == 0 && !used[x][y]) {if(x == grid.length-1 && y == grid[0].length-1) {return res;}used[x][y] = true;queue.offer(new Point(x-1, y-1));queue.offer(new Point(x-1, y));queue.offer(new Point(x, y-1));queue.offer(new Point(x+1, y-1));queue.offer(new Point(x+1, y+1));queue.offer(new Point(x+1, y));queue.offer(new Point(x, y+1));queue.offer(new Point(x-1, y+1));}}res++;}return -1;}public static class Point {public int x;public int y;public Point(int x, int y) {this.x = x;this.y = y;}}