建设网站 万网,软装设计理念,网络营销课程论文,网站建设框架图第一题
695. 岛屿的最大面积 本题解法#xff1a;采用bfs的算法#xff1b; 本题使用象限数组的遍历方法和定义布尔数组vis来遍历每一个元素的上下左右元素#xff0c;防治被遍历的元素被二次遍历#xff1b; 本题具体分析如上题故事#xff0c;但是由于要求区域的最大面…第一题
695. 岛屿的最大面积 本题解法采用bfs的算法 本题使用象限数组的遍历方法和定义布尔数组vis来遍历每一个元素的上下左右元素防治被遍历的元素被二次遍历 本题具体分析如上题故事但是由于要求区域的最大面积所以在bfs方法中找到合适的元素进行入队列操作时我们要对其个数进行统计 至此代码如下 class Solution {//象限坐标数组int[] dx {0,0,1,-1};int[] dy {1,-1,0,0};boolean[][] vis new boolean[51][51];int m,n;public int maxAreaOfIsland(int[][] grid) {m grid.length;n grid[0].length;int ret 0;//统计最大面积for(int i 0;i m ;i){for(int j 0;j n ;j){if(grid[i][j] 1 !vis[i][j]){ret Math.max(ret,bfs(grid,i,j));}}}return ret;}public int bfs(int[][] grid,int i,int j){int cot 0;Queueint[] q new LinkedList();q.add(new int[]{i,j});vis[i][j] true;cot;while(!q.isEmpty()){int[] t q.poll();int a t[0],b t[1];for(int s 0;s 4;s){int x a dx[s],y b dy[s];if(x 0 x m y 0 y n grid[x][y] 1 !vis[x][y]){q.add(new int[]{x,y});vis[x][y] true;cot;}} }return cot;}
} 第二题
130. 被围绕的区域 解法bfs层序遍历 解题步骤如下 步骤一 如上图所示首先遍历第一行最后一行第一列最后一列的元素查找与其相邻的元素并将这些元素o变成符号* 步骤二 遍历整个图像中所有的元素遇到的o字符变成x字符遇到的*字符变成o字符如此满足题意 至此代码如下 class Solution {//象限坐标数组int[] dx {0,0,1,-1};int[] dy {1,-1,0,0};int m,n;public void solve(char[][] board) {m board.length;n board[0].length;//1、先处理边界的0全部修改成*//修改第一行和最后一行for(int j 0;j n;j){if(board[0][j] O ) bfs(board,0,j);if(board[m-1][j] O ) bfs(board,m-1,j);}//修改第一列和最后一列for(int i 0;i m;i){if(board[i][0] O ) bfs(board,i,0);if(board[i][n-1] O ) bfs(board,i,n-1);}//2、还原将剩下的0变成x将边缘的*变为0for(int i 0;i m;i){for(int j 0;j n ;j){if(board[i][j] O) board[i][j] X;else if(board[i][j] *) board[i][j] O;}}}public void bfs(char[][] board,int i,int j){Queueint[] q new LinkedList();q.add(new int[]{i,j});board[i][j] *;while(!q.isEmpty()){int[] t q.poll();int a t[0],b t[1];for(int s 0;s 4;s){int x a dx[s],y b dy[s];if(x 0 x m y 0 y n board[x][y] O ){board[x][y] *;q.add(new int[]{x,y});}} }}
} 第三题
1926. 迷宫中离入口最近的出口 本题的题目类型可以理解为边权为1的最短路问题 迷宫游戏其数据结构模拟一个迷宫矩阵当每一个二维坐标相对性的字符为则是路障坐标对应的字符为.,则表示是可以前进的路当前我们所在的位置就是一个二维坐标对应的坐标 由于我们的安全出口的路线就是从给定的位置开始移动移动到边界且在所能到达安全出口的所有路线里面返回最短的路线即最少的移动次数 我们在遍历当前位置的上下左右合法位置的时候采用的象限数组的方法同时由于移动之后我们不能原路返回所以采用定义布尔数组vis给每一个遍历过的位置在该数组里面定义为true防治二次遍历 我们将初识位置放于队列中将该位置的上下左右位置都进行过遍历每遍历到一个合法的位置就将该位置放于队列中且定义的统计移动次数的cot加一当遍历到矩阵的边界时候返回最短的cot变量 至此代码如下 class Solution {//象限坐标数组int[] dx {0,0,1,-1};int[] dy {1,-1,0,0};public int nearestExit(char[][] maze, int[] entrance) {int m maze.length,n maze[0].length;boolean[][] vis new boolean[m][n];Queueint[] q new LinkedList();q.add(new int[]{entrance[0],entrance[1]});vis[entrance[0]][entrance[1]] true;int step 0;while(!q.isEmpty()){step;int sz q.size();for(int i 0;i sz;i){int[] t q.poll();int a t[0],b t[1];for(int j 0;j4;j){int x a dx[j],y b dy[j];if(x 0 x m y 0 y n maze[x][y] . !vis[x][y]){//判断是否已经走出出口if(x 0|| x m-1 || y 0 || y n-1) return step;q.add(new int[]{x,y});vis[x][y] true;}}}}return -1;}
} ps本次的内容就到这里了如果对你有所帮助的话就请一键三连哦
