递归、搜索与回溯算法 - 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 和 prev
m = 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 重新弄为0
count = 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 和 n
m = 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 和列数 n
int[] 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; // 网格的行数、列数以及限制条件 k
boolean[][] 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，则返回 true
return 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; // 初始化备忘录为 -1
return 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 开始计数
// 向后递归一下，把较大的值赋值给 ret
for(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) {
// 如果左边界大于或等于右边界，说明只剩一个数字或者范围无效，代价为 0
if (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 和 memo
m = 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;
}
}
