湘潭网站建设方案表格,做网站接单渠道,北京环球影城必须存包的项目,wordpress文章标题插件目录
1、图像渲染
1.1 算法原理
1.2 算法代码
2、岛屿数量
2.1 算法原理
2.2 算法代码
3、岛屿的最大面积
3.1 算法原理
3.2 算法代码
4、被围绕的区域
4.1 算法原理 4.2 算法代码
5、太平洋大西洋水流问题
5.1 算法原理
5.2 算法代码
6、扫雷游戏
6.1 算法原理…目录
1、图像渲染
1.1 算法原理
1.2 算法代码
2、岛屿数量
2.1 算法原理
2.2 算法代码
3、岛屿的最大面积
3.1 算法原理
3.2 算法代码
4、被围绕的区域
4.1 算法原理 4.2 算法代码
5、太平洋大西洋水流问题
5.1 算法原理
5.2 算法代码
6、扫雷游戏
6.1 算法原理
6.2 算法代码
7、衣橱整理 原面试题 13. 机器人的运动范围
7.1 算法原理
7.2 算法代码 1、图像渲染 . - 力扣LeetCode 1.1 算法原理
从(sr,sc)位置开始上下左右暴搜将区域中符合条件的值修改为color。细节问题当 color image[sr][sc]时不需修改直接返回即可。 1.2 算法代码
class Solution {int[] dx, dy;int[][] image;int color;int n, m;int val;public int[][] floodFill(int[][] image_, int sr, int sc, int color_) {if(color_ image_[sr][sc]) return image_;image image_;val image[sr][sc];color color_;n image.length;m image[0].length;dx new int[]{-1, 1, 0, 0};dy new int[]{0, 0, -1, 1};image[sr][sc] color;dfs(sr, sc);return image;}public void dfs(int i, int j) {for(int k 0; k 4; k) {int x i dx[k];int y j dy[k];if(x 0 x n y 0 y m image[x][y] val) {image[x][y] color;dfs(x, y);}}}
} 2、岛屿数量 . - 力扣LeetCode 2.1 算法原理
全局变量
boolean[][] check;//是否来过int ret;//返回值int[] dx;//横坐标上下左右int[] dy;//纵坐标上下左右
思想
遍历矩阵每次来到新的1区域将这个区域中的所有1位置做好标记(check置为false)ret返回ret 2.2 算法代码
class Solution {int[] dx {1, -1, 0, 0};int[] dy {0, 0, 1, -1};boolean[][] check;int ret;int m, n;public int numIslands(char[][] grid) {m grid.length;n grid[0].length;check new boolean[m][n];for(int i 0; i m ; i) {for(int j 0; j n; j) {if(check[i][j] false grid[i][j] 1) {ret;check[i][j] true;dfs(grid, i, j);}}}return ret;}public void dfs(char[][] grid, int i, int j) {for(int k 0; k 4; k) {int x i dx[k];int y j dy[k];if(x 0 x m y 0 y n grid[x][y] 1 !check[x][y]) {check[x][y] true;dfs(grid, x, y);}}}
} 3、岛屿的最大面积 . - 力扣LeetCode 3.1 算法原理
与上题基本一致选出面积最大值即可
暴搜count记录每块陆地的最大面积(每次进入dfscount)ret记录所有陆地的最大面积(选出count的最大值) 3.2 算法代码
class Solution {int[] dx {1, -1, 0, 0};int[] dy {0, 0, 1, -1};boolean[][] check;int ret;int m, n;int count;public int maxAreaOfIsland(int[][] grid) {m grid.length;n grid[0].length;check new boolean[m][n];for(int i 0; i m ; i) {for(int j 0; j n; j) {if(check[i][j] false grid[i][j] 1) {count 0;check[i][j] true;dfs(grid, i, j);//统计一块陆地的面积ret Math.max(ret, count);}}}return ret;}public void dfs(int[][] grid, int i, int j) {count; for(int k 0; k 4; k) {int x i dx[k];int y j dy[k];if(x 0 x m y 0 y n grid[x][y] 1 !check[x][y]) {check[x][y] true;dfs(grid, x, y);}}}
} 4、被围绕的区域 . - 力扣LeetCode 4.1 算法原理 本题采用“正难则反”法则既然我们无法区分边缘区域与内部区域那么就先对矩阵的边缘区域进行操作
对边缘区域的所有O区域进行深搜修改为.此时边缘区域的O已全部修改为.内部区域的O仍为O再遍历整个矩阵.重新修改为O(边缘区域的O)O则修改为X(内部区域的O) 4.2 算法代码
class Solution {int m, n;int[] dx { 1, -1, 0, 0 };int[] dy { 0, 0, 1, -1 };public void solve(char[][] board) {m board.length;n board[0].length;for (int i 0; i m; i) {for (int j 0; j n; j) {//把边缘区域的O置为.if ((i 0 || i m - 1 || j 0 || j n - 1) board[i][j] O) {board[i][j] .;dfs(board, i, j);}}}for (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 dfs(char[][] board, int i, int j) {for (int k 0; k 4; k) {int x i dx[k];int y j dy[k];if (x 0 x m y 0 y n board[x][y] O) {board[x][y] .;dfs(board, x, y);}}}
} 5、太平洋大西洋水流问题 . - 力扣LeetCode 5.1 算法原理
本题仍采用“正难则反”原则
从海岸反向记录可流入海洋的位置分别标记哪些位置可流入太平洋boolean[][] pac可流入则标为true分别标记哪些位置可流入大西洋boolean[][] atl可流入则标为truepac、atl中均为true的位置说明均可流入两大海洋。 5.2 算法代码
class Solution {int[] dx {1, -1, 0, 0};int[] dy {0, 0, 1, -1};int m, n;public ListListInteger pacificAtlantic(int[][] heights) {m heights.length;n heights[0].length;boolean[][] pac new boolean[m][n];//标记太平洋可流入的位置boolean[][] atl new boolean[m][n];//标记大西洋可流入的位置//pacfor(int j 0; j n; j) dfs(heights, 0, j, pac);for(int i 0; i m; i) dfs(heights, i, 0, pac);//atlfor(int j 0; j n; j) dfs(heights, m - 1, j, atl);for(int i 0; i m; i) dfs(heights, i, n - 1, atl);//都可流入的位置ListListInteger ret new ArrayList();for(int i 0; i m; i) {for(int j 0; j n; j) {if(pac[i][j] atl[i][j]) {ListInteger list new ArrayList();list.add(i);list.add(j);ret.add(list);}}}return ret;}public void dfs(int[][] heights, int i, int j, boolean[][] check) {check[i][j] true;int cur heights[i][j];for(int k 0; k 4; k) {int x i dx[k];int y j dy[k];if(x 0 x m y 0 y n check[x][y] false heights[x][y] cur) {dfs(heights, x, y, check);}}}
} 6、扫雷游戏 . - 力扣LeetCode 6.1 算法原理
本题主要节目就是dfs及回溯如果相邻没有地雷的空方块被挖出则将其上下左右及四角方向全部递归揭露所有和其相邻的未挖出的方块直至相邻的方块的周围有地雷则将周围有地雷的方块标为地雷的数量。
对于斜方向上我们只需在dx和dy数组上的对应位置上加上相应值即可。 6.2 算法代码
class Solution {char[][] board;int[] dx {0, 0, 1, -1, -1, -1, 1, 1};int[] dy {1, -1, 0, 0, -1, 1, -1, 1};int m, n;public char[][] updateBoard(char[][] board_, int[] click) {board board_;m board.length;n board[0].length;int sx click[0], sy click[1];char ch board[sx][sy];if(ch M) {board[sx][sy] X;return board;}if(ch B) return board;dfs(sx, sy);return board;}public void dfs(int i, int j) {int count 0;for(int k 0; k 8; k) {int x i dx[k];int y j dy[k];if(x 0 x m y 0 y n board[x][y] M) {count;}}if(count ! 0) {//周围有地雷board[i][j] (char)(count 0);return;}else {//周围没有地雷board[i][j] B;for(int k 0; k 8; k) {int x i dx[k], y j dy[k];if(x 0 x m y 0 y n board[x][y] E) {dfs(x, y);}}}}
} 7、衣橱整理 原面试题 13. 机器人的运动范围 . - 力扣LeetCode 7.1 算法原理
直接dfs洪水灌溉需要注意的是:
每个位置不能重复进入横纵下标的每个位的数值之和不能超过cnt 7.2 算法代码
class Solution {int ret;int[] dx { 1, -1, 0, 0 };int[] dy { 0, 0, 1, -1 };int m, n;boolean[][] check;public int wardrobeFinishing(int m_, int n_, int cnt) {m m_;n n_;check new boolean[m][n];dfs(0, 0, cnt);return ret;}public void dfs(int i, int j, int cnt) {check[i][j] true;ret;for (int k 0; k 4; k) {int x i dx[k];int y j dy[k];if (x 0 x m y 0 y n !check[x][y] isRight(x, y, cnt)) {dfs(x, y, cnt);}}}public boolean isRight(int x, int y, int cnt) {int sum 0;while (x ! 0) {sum x % 10;x / 10;}while (y ! 0) {sum y % 10;y / 10;}return sum cnt;}
} END
