关键词 网站,网页设计教程入门,h5页面制作软件下载下来要钱吗,什么是搜索引擎优化一、二维网格图中探测环
题意:
给定一个二维数组grid,如果二维数组中存在一个环#xff0c;处于环上的值都是相同的。返回true#xff1b;如果不存在就返回false#xff1b;
思路#xff1a;
在以往的dfs搜索中#xff0c;都是往四个方向去dfs#xff1b;但是在这一道…一、二维网格图中探测环
题意:
给定一个二维数组grid,如果二维数组中存在一个环处于环上的值都是相同的。返回true如果不存在就返回false
思路
在以往的dfs搜索中都是往四个方向去dfs但是在这一道题中四个方向是不行的如果第i次是从左往右过来的那么i1次就不能从右往左再过
去。所以应该加上这个判断。
那我们就要走dfs函数上多加一个参数from。
如果上一次不是从左边来的那我们就可以往左走
如果上一次不是从右边来的那我们就可以往右走
以此类推 public void dfs(int x, int y, char ch, char from) {if (x 0 || x m || y 0 || y n || grid[x][y] ! ch) {return;}if (visited[x][y]) {hasRing true;return;}visited[x][y] true;if (from ! L)dfs(x, y - 1, ch, R);if (from ! R)dfs(x, y 1, ch, L);if (from ! U)dfs(x-1, y, ch, D);if (from ! D)dfs(x1, y, ch, U);}
代码
class Solution {boolean[][] visited;char[][] grid;int m, n;boolean hasRing;public boolean containsCycle(char[][] grid) {m grid.length;n grid[0].length;visited new boolean[m][n];this.grid grid;for (int i 0; i m; i) {for (int j 0; j n; j) {if (!visited[i][j]) {dfs(i, j, grid[i][j], L);if (hasRing) return true;}}}return false;}public void dfs(int x, int y, char ch, char from) {if (x 0 || x m || y 0 || y n || grid[x][y] ! ch) {return;}if (visited[x][y]) {hasRing true;return;}visited[x][y] true;if (from ! L)dfs(x, y - 1, ch, R);if (from ! R)dfs(x, y 1, ch, L);if (from ! U)dfs(x-1, y, ch, D);if (from ! D)dfs(x1, y, ch, U);}
}
二、最大人工岛
思路:
1.首先找到所有的岛屿(连通块)将他们存储到map表中。可以使用一个值来标识一个连通块。 MapInteger,Integer mapnew HashMap();for(int i0;in;i){for(int j0;jn;j){if(grid[i][j]1){int areadfs(grid,i,j,islandIdx);//计算每一个连通块的大小map.put(islandIdx,area);//然后放到map里面保存islandIdx;//maxAreaMath.max(area,maxArea);}}}
2.将所有的连通块找出来之后然后枚举所有的海洋块。判断海洋块的周围有没有两个连通块(最多只能有两个连通块)。在枚举的同时比较得出最大面积值。 //枚举所有0的上下左右可能连接的情况for(int i0;in;i){for(int j0;jn;j){SetInteger setnew HashSet();if(grid[i][j]0){//左边的格子 如果是岛屿 就把岛屿编号放进来if(i-10grid[i-1][j]2){set.add(grid[i-1][j]);}if(i1ngrid[i1][j]2){set.add(grid[i1][j]);}if(j-10grid[i][j-1]2){set.add(grid[i][j-1]);}if(j1ngrid[i][j1]2){set.add(grid[i][j1]);}int curMaxArea1;for(Integer index:set){int otherAreamap.get(index);curMaxAreaotherArea;}maxAreaMath.max(maxArea,curMaxArea);}}}
代码
class Solution {int n;public int largestIsland(int[][] grid) {ngrid.length;int maxArea0,islandIdx2;//对所有岛屿编号并记录在哈希表中MapInteger,Integer mapnew HashMap();for(int i0;in;i){for(int j0;jn;j){if(grid[i][j]1){int areadfs(grid,i,j,islandIdx);//计算每一个连通块的大小map.put(islandIdx,area);//然后放到map里面保存islandIdx;//maxAreaMath.max(area,maxArea);}}}//枚举所有0的上下左右可能连接的情况for(int i0;in;i){for(int j0;jn;j){SetInteger setnew HashSet();if(grid[i][j]0){//左边的格子 如果是岛屿 就把岛屿编号放进来if(i-10grid[i-1][j]2){set.add(grid[i-1][j]);}if(i1ngrid[i1][j]2){set.add(grid[i1][j]);}if(j-10grid[i][j-1]2){set.add(grid[i][j-1]);}if(j1ngrid[i][j1]2){set.add(grid[i][j1]);}int curMaxArea1;for(Integer index:set){int otherAreamap.get(index);curMaxAreaotherArea;}maxAreaMath.max(maxArea,curMaxArea);}}}return maxArea; }public int dfs(int[][] grid,int x,int y,int count){if(!isArea(grid,x,y)||grid[x][y]count||grid[x][y]!1)return 0;grid[x][y]count;return 1dfs(grid,x-1,y,count)dfs(grid,x1,y,count)dfs(grid,x,y-1,count)dfs(grid,x,y1,count);}public boolean isArea(int[][] grid, int x, int y) {if (x n || x 0 || y 0 || y n)return false;return true;}
}
