递归、搜索与回溯算法 - 3 （ floodfill 记忆化搜素 9000 字详解 ）

一：floodfill 算法

1.1 图像渲染

题目链接：图像渲染

class Solution {// 首先先定义四个方向的向量int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};// 接着用 m 记录行数，n 记录列数，prev 记录 (sr， sc) 位置的原始数值int m, n, prev;public int[][] floodFill(int[][] image, int sr, int sc, int color){// 如果起始像素的颜色已经是目标颜色，则无需填充if (image[sr][sc] == color) return image;// 先初始化一下 m，n 和 prevm = image.length;n = image[0].length;prev = image[sr][sc];// 接着调用 dfs 函数，调用后直接返回 image 即可dfs(image, sr, sc, color);return image;}public void dfs(int[][] image, int i, int j, int color){// 首先先把当前位置的值修改成 color 的值image[i][j] = color;// 接着开始遍历这个位置的四个方向for(int k = 0; k < 4; k++){int x = dx[k] + i, y = dy[k] + j;// 判断新位置是否合法：在边界内且颜色与初始颜色相同if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev) dfs(image, x, y, color);          }}
}

1.2 岛屿数量

题目链接：岛屿数量

class Solution {// 先定义四个方向int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};// 再定义一个 vis 数组，用于标记当前的陆地是否被访问过, m 记录行数，n 记录列数boolean[][] vis;int m, n;public int numIslands(char[][] grid){// 接着先初始化一下 m， n 以及 vis ，并定义一个 ret 用于记录最终的结果m = grid.length;n = grid[0].length;vis = new boolean[m][n];int ret = 0;// 接着开始遍历网格中的每一个陆地，当遍历一个陆地后把这个陆地所属的岛屿的陆地全部标记为已访问的状态for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(!vis[i][j] && grid[i][j] == '1'){ret++;dfs(grid, i, j);}}}return ret;}public void dfs(char[][] grid, int i, int j){// 首先先把当前位置标记为已访问的状态vis[i][j] = true;// 接着去处理这个位置的四个方向for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];// 如果 x 和 y 不越界，并且 (i, j) 位置没有被访问过且这个位置是陆地，那么就继续递归，把这个位置当作新的起点if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == '1') dfs(grid, x, y);            }}
}

1.3 岛屿的最大面积

题目链接：岛屿的最大面积

class Solution {// 先定义四个方向以及 vis 数组，vis 数组用于标记当前陆地是否被访问过， count 用于记录当前岛屿的面积，m 用于记录行数，n 用于记录列数int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};boolean[][] vis;int count, m ,n;public int maxAreaOfIsland(int[][] grid){// 先初始化一下全局变量，并定义 ret 用于记录最终的结果m = grid.length;n = grid[0].length;vis = new boolean[m][n];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]){// 每次循环都把 count 重新弄为0count = 0;dfs(grid, i, j);// 调用完 dfs 函数后开始更新 ret 的值ret = Math.max(ret, count);}}}return ret; // 循环结束后返回 ret}public void dfs(int[][] grid, int i, int j){// 首先把当前位置标记为已访问过的状态,并增加计数vis[i][j] = true;count++;// 接着开始处理这个位置的四个方向for(int k = 0; k < 4; k++){int x = dx[k] + i, y = dy[k] + j;if(x >=0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]){dfs(grid, x, y); // 递归处理这个位置的四个方向}}}
}

1.4 被围绕的区域

题目链接：被围绕的区域

class Solution {// 先定义四个方向,并用 m 记录行数，n 记录列数int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};int m, n;public void solve(char[][] board){// 初始化一下 m 和 nm = board.length;n = board[0].length;// 下面处理一下 board 的边界 0，首先处理第一行和最后一行for(int j = 0; j < n; j++){if (board[0][j] == 'O') dfs(board, 0, j);if (board[m - 1][j] == 'O') dfs(board, m - 1, j);}// 接着处理第一列和最后一列for(int i = 0; i < m; i++){if(board[i][0] == 'O') dfs(board, i, 0);if(board[i][n - 1] == 'O') dfs(board, i, n - 1);}// 处理完边界情况后开始正常处理 board 中的 0，找到 0 后进行深度优先遍历即可for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(board[i][j] == '.') board[i][j] = 'O';else if(board[i][j] == 'O') board[i][j] = 'X';}}}public void dfs(char[][] board, int i, int j){// 首先先把当前位置标记为 . board[i][j] = '.';// 接着去处理这个位置的四个方向for(int k = 0; k < 4; k++){int x = dx[k] + i, y = dy[k] + j;if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O'){dfs(board, x, y);}}}
}

1.5 太平洋大西洋水流问题

题目链接：太平洋大西洋水流问题

class Solution {// 首先定义一下四个方向，并定义一下行数 m 和列数 nint[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};int m, n;public List<List<Integer>> pacificAtlantic(int[][] heights){// 初始化一下 m 和 n，再根据 m 和 n 初始化一下两个标记数组m = heights.length;n = heights[0].length;// pac 数组的值为 true 代表从太平洋出发，能到达这个点boolean[][] pac = new boolean[m][n];boolean[][] atl = new boolean[m][n];// 接着先遍历太平洋的边，即第一行和第一列for(int j = 0; j < n; j++) dfs(heights, 0, j, pac);for(int i = 0; i < m; i++) dfs(heights, i, 0, pac);// 接着再遍历大西洋的边，即最后一行和最后一列for(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);// 接着提取结果List<List<Integer>> ret = new ArrayList<>();for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(pac[i][j] == true && atl[i][j] == true){List<Integer> tmp = new ArrayList<>();tmp.add(i);tmp.add(j);ret.add(tmp);}}}return ret;}/*** 深度优先搜索 (DFS)：标记能流入某个洋的格子* @param h 高度矩阵* @param i 当前格子的行坐标* @param j 当前格子的列坐标* @param vis 标记数组（用于标记是否能流入太平洋或大西洋）*/public void dfs(int[][] h, int i, int j, boolean[][] vis){// 首先先把当前位置标记为 true vis[i][j] = true;// 接着处理一下这个位置的四个方向for(int k = 0; k < 4; k++){int x = dx[k] + i, y = dy[k] + j;if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && h[x][y] >= h[i][j]){dfs(h, x, y, vis);}}}
}

1.6 扫雷游戏

题目链接：扫雷游戏

class Solution {// 定义八个方向的移动向量，用于表示上下左右以及四个对角线方向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){// 先初始化一下 m 和 n,接着获取一下点击位置的坐标m = board.length;n = board[0].length;int x = click[0], y = click[1];// 接着判断一下这个点是地雷还是空白字符if(board[x][y] == 'M'){board[x][y] = 'X';return board; // 直接结束游戏}else{// 否则挖到的是空白方块dfs(board, x, y);return board; // 返回更新过后的 board}}/*** 深度优先搜索 (DFS)：更新棋盘* @param board 当前的扫雷棋盘* @param i 当前的行坐标* @param j 当前的列坐标*/public void dfs(char[][] board, int i, int j){// 首先统计一下当前位置旁边的地雷个数int count = 0;for(int k = 0; k < 8; k++){int x = dx[k] + i, y = dy[k] + j;if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M')  count++;}// 接着根据 count 的个数分情况讨论，如果为 0 则修改成 B 如果不为 0 则修改成数字if(count == 0){board[i][j] = 'B'; // 标记当前格子为空白for(int k = 0; k < 8; k++){int x = dx[k] + i, y = dy[k] + j;if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E'){dfs(board, x, y);}}}else{// 将当前位置标记为周围地雷的数量（'1'-'8'）board[i][j] = (char) ('0' + count);return; // 如果是数字就不再递归了}}
}

1.7 衣橱整理

题目链接：衣橱整理

class Solution {int m, n, k; // 网格的行数、列数以及限制条件 kboolean[][] vis; // 用于记录某个位置是否已被访问int ret; // 记录可以到达的格子数量int[] dx = {1, -1, 0, 0}; int[] dy = {0, 0, 1, -1}; public int wardrobeFinishing(int _m, int _n, int _k) {// 初始化全局变量m = _m;n = _n;k = _k;vis = new boolean[m][n]; // 从起点 (0, 0) 开始深度优先搜索dfs(0, 0);return ret;}/*** 深度优先搜索 (DFS)：从当前格子开始递归探索可达的格子* @param i 当前格子的行坐标* @param j 当前格子的列坐标*/public void dfs(int i, int j) {// 访问当前格子，增加计数，并标记当前格子为已访问ret++;vis[i][j] = true; // 接着遍历四个方向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 && !vis[x][y] && check(x, y)) {dfs(x, y); }}}/*** 判断某个格子的坐标是否满足位数和限制条件* @param i 行坐标* @param j 列坐标* @return 如果位数和小于等于 k，则返回 true，否则返回 false*/public boolean check(int i, int j) {int tmp = 0; // 存储行坐标和列坐标的位数和// 计算行坐标的各位数字之和while (i != 0) {tmp += i % 10;i /= 10;}// 计算列坐标的各位数字之和while (j != 0) {tmp += j % 10;j /= 10;}// 如果位数和小于等于 k，则返回 truereturn tmp <= k;}
}

二：记忆化搜索

2.1 斐波那契数列 (必看)

题目链接：斐波那契数列 (必看)

class Solution {// 记忆化搜索实现int[] memo; // 备忘录public int fib(int n) {memo = new int[n + 1];for (int i = 0; i <= n; i++) memo[i] = -1; // 初始化备忘录为 -1return dfs(n);}public int dfs(int n) {if (memo[n] != -1) return memo[n]; // 如果已经计算过，直接返回备忘录中的值if (n == 0 || n == 1) {memo[n] = n; // 边界情况return n;}memo[n] = dfs(n - 1) + dfs(n - 2); // 递归返回时把结果放在备忘录里return memo[n];}
}

class Solution {// 动态规划实现public int fib(int n) {if (n == 0) return 0;if (n == 1) return 1;int[] dp = new int[n + 1]; // 用于存储子问题的结果dp[0] = 0;dp[1] = 1;// 计算斐波那契数列for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

2.2 不同路径

题目链接：不同路径

class Solution {public int uniquePaths(int m, int n){// 记忆化搜索解法// 先创建一个备忘录 memo int[][] memo = new int[m + 1][n + 1];return dfs(m, n, memo);}// 递归函数：计算到达位置 (i, j) 的路径数public int dfs(int i, int j, int[][] memo){// 首先先看看备忘录中有没有if(memo[i][j] != 0) return memo[i][j];// 处理一下越界的情况if(i == 0 || j == 0) return 0;// 处理一下起点if(i == 1 && j == 1) return 1;// 如果备忘录没有就开始递归,递归前记录一下值memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);return memo[i][j];}
}

2.3 最长递增子序列

题目链接：最长递增子序列

class Solution {public int lengthOfLIS(int[] nums){// 记忆化搜索实现// 先根据 nums 的长度初始化 memo 数组int n = nums.length;int[] memo = new int[n];// 接着枚举一下每个位置的 dfs 值，把较大的值放入 ret 中int ret = 0;for(int i = 0; i < n; i++){ret = Math.max(ret, dfs(i, nums, memo));}return ret;}// 递归函数：计算从位置 pos 开始的最长上升子序列长度public int dfs(int pos, int[] nums, int[] memo){// 首先先看看备忘录里有没有这个 dfs 值if(memo[pos] != 0) return memo[pos];int ret = 1; // 因为路径是包含自己的，所以我们从 1 开始计数// 向后递归一下，把较大的值赋值给 retfor(int i = pos + 1; i < nums.length; i++){if(nums[i] > nums[pos]){ret = Math.max(ret, dfs(i, nums, memo) + 1);}}// 记录当前计算结果memo[pos] = ret;return ret;}
}

class Solution {public int lengthOfLIS(int[] nums) {// 动态规划实现int n = nums.length;// dp[i] 表示以 nums[i] 作为结尾的最长上升子序列的长度int[] dp = new int[n];// 初始化 dp 数组，每个位置最少包含自身一个元素Arrays.fill(dp, 1);int ret = 0; // 记录最长上升子序列的长度// 从后往前填表for (int i = n - 1; i >= 0; i--) {// 从 i 的后一个元素开始遍历for (int j = i + 1; j < n; j++) {// 如果 nums[j] > nums[i]，说明可以将 nums[j] 接在 nums[i] 后面if (nums[j] > nums[i]) {// 更新 dp[i]，选择最长的子序列dp[i] = Math.max(dp[i], dp[j] + 1);}}ret = Math.max(ret, dp[i]);}return ret;}
}

2.4 猜数字大小 II

题目链接：猜数字大小 II

class Solution {// 用于存储递归结果的备忘录数组，memo[i][j] 表示区间 [i, j] 的最小代价int[][] memo;public int getMoneyAmount(int n) {// 先初始化备忘录memo = new int[n + 1][n + 1];// 从 [1, n] 开始return dfs(1, n);}// 递归函数：计算区间 [left, right] 的最小代价public int dfs(int left, int right) {// 如果左边界大于或等于右边界，说明只剩一个数字或者范围无效，代价为 0if (left >= right) return 0;// 如果该区间已经计算过，直接返回备忘录中的值if (memo[left][right] != 0) {return memo[left][right];}int ret = Integer.MAX_VALUE;// 枚举当前区间 [left, right] 中的所有数字作为猜测点for (int head = left; head <= right; head++) {// 递归计算左区间 [left, head - 1] 的最小代价int x = dfs(left, head - 1);// 递归计算右区间 [head + 1, right] 的最小代价int y = dfs(head + 1, right);// 选择左区间和右区间中较大的代价，并加上当前猜测点的代价int cost = Math.max(x, y) + head;// 更新当前区间的最小代价ret = Math.min(ret, cost);}// 将结果存入备忘录中memo[left][right] = ret;// 返回当前区间的最小代价return ret;}
}

2.5 矩阵中的最长递增路径

题目链接：矩阵中的最长递增路径

class Solution {// 先定义一下四个方向，并用·m 记录行号，n 记录列号，用 memo 当作一个备忘录,用于存储从每个点开始的最长递增路径的长度int m, n;int[] dx = {1, -1, 0, 0};int[] dy = {0, 0, 1, -1};int[][] memo;public int longestIncreasingPath(int[][] matrix){// 先初始化一下 m，n 和 memom = matrix.length;n = matrix[0].length;memo = new int[m][n];// 暴力枚举所有位置的长度，接着取出最大值int ret = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){ret = Math.max(ret, dfs(matrix, i, j));}}return ret;}// 深度优先搜索函数：计算从位置 (i, j) 开始的最长递增路径的长度public int dfs(int[][] matrix, int i, int j){// 先判断一下备忘录里有没有这个值if(memo[i][j] != 0) return memo[i][j];// ret 初始化为 1 ，因为自己也算int ret = 1;for(int k = 0; k < 4; k++){int x = dx[k] + i, y = dy[k] + j;if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]){ret = Math.max(ret, dfs(matrix, x, y) + 1);}}// 结果返回前先把结果存入备忘录中memo[i][j] = ret;return ret;}
}