当前位置： 首页 > article >正文

DFS算法专题(四)——综合练习【含矩阵回溯】【含3道力扣困难级别算法题】

article 2024/11/17 22:08:46

目录

1、字母大小写全排列

1.1 算法原理

1.2 算法代码

2、优美的排列

2.1 算法原理

2.2 算法代码

3、N皇后【困难】★★★

3.1 算法原理

 3.2 算法代码

4、有效的数独【解数独铺垫】

4.1 算法原理

4.2 算法代码

5、解数独【困难】★★★

5.1 算法原理

5.2 算法代码 

6、单词搜索

6.1 算法原理

​6.2 算法代码

7、黄金矿工

7.1 算法原理

7.2 算法代码

 8、不同路径 III【困难】★★★

8.1 算法原理

8.2 算法代码

1、字母大小写全排列

1.1 算法原理

全局变量：ret；path；

函数体：dfs(...,pos);//pos为要添加的字符的下标。

算法思想：遍历字符串，如果遇到的是字母字符，分大写和小写两个分支；如果遇到的是数字字符，则直接添加进path路径中。

函数出口：遇到叶子节点，即pos==s.length时，添加进ret中，返回。

回溯：path.deleteCharAt(path.size() - 1)；--> 恢复现场

1.2 算法代码

class Solution {
    List<String> ret;
    StringBuffer path;

    public List<String> letterCasePermutation(String ss) {
        ret = new ArrayList<>();
        path = new StringBuffer();
        char[] s = ss.toCharArray();
        dfs(s, 0);
        return ret;
    }

    public void dfs(char[] s, int pos) {
        if(pos == s.length) {
            ret.add(path.toString());
            return;
        }
        char ch = s[pos];
        //不变(不管是数字字符还是字母都有不变的分支)
        path.append(ch);
        dfs(s, pos + 1);
        //回溯
        path.deleteCharAt(path.length() - 1);

        //变
        if(ch < '0' || ch > '9') {
            char tmp = change(ch);
            path.append(tmp);
            dfs(s, pos + 1);
            //回溯
            path.deleteCharAt(path.length() - 1);
        }
    }
    public char change(char ch) {
        if(ch >= 'a' && ch <= 'z') return ch -= 32;
        else return ch += 32;
    }
}

2、优美的排列

. - 力扣（LeetCode）

2.1 算法原理

突破口：决策树

  • 全局变量：ret；boolean[n+1] check//记录数据是否已被使用
  • 函数头：dfs(pos,...)//pos记录该往哪个下标处放元素
  • 函数出口：pos == n+1(下标从1开始)
  • 剪枝：①剪去被使用过的元素的分支②减去 数值/下标 不可被下标/数值 整除的分支
  • 回溯：恢复check

2.2 算法代码

class Solution {
    int ret;
    boolean[] check;
    public int countArrangement(int n) {
        check = new boolean[n + 1];
        dfs(n, 1);
        return ret;
    }
    public void dfs(int n, int pos) {
        if(pos == n + 1) {
            ret++;
        }
        for(int i = 1; i <= n; i++) {
            if(check[i] == false && (i % pos == 0 || pos % i == 0)) {
                check[i] = true;
                dfs(n, pos + 1);
                //回溯
                check[i] = false;
            }
        }
    }
}

3、N皇后【困难】★★★

. - 力扣（LeetCode）

3.1 算法原理

主要思想：一行一行的放，本层放了以后，去考虑下一层。

重点：如何剪枝？

  • 判断 该行&该列&该主对角线&该副对角线是否有'Q'
  • boolean[] col;//判断该列是否有'Q'
  • boolean[] dig1;//判断该主对角线是否有'Q'
  • boolean[] dig2;//判断该副对角线是否有'Q'

列的判断很容易 --> 放入'Q'后，将该列使用col数组标记；

但是主对角线&副对角线该如何判断呢？--> 数学知识

  1. 主对角线的判断：y=x+b --> y-x=b --> y-x+n=b+n(避免越界)
  2. 副对角线的判断：y = -x + b --> y + x = b

 3.2 算法代码

class Solution {
    List<List<String>> ret;
    char[][] path;
    boolean[] colCheck;
    boolean[] dig1Check;// 判断主对角线
    boolean[] dig2Check;// 判断副对角线
    int n;

    public List<List<String>> solveNQueens(int n_) {
        n = n_;
        ret = new ArrayList<>();
        path = new char[n][n];
        for(int i = 0; i < n; i++) 
            for(int j = 0; j < n; j++) path[i][j] = '.';
        colCheck = new boolean[n];
        dig1Check = new boolean[n * 2];
        dig2Check = new boolean[n * 2];
        dfs(0);
        return ret;
    }
    public void dfs(int row) {
        if(row == n) {
            //函数出口 & 完整的皇后棋盘的放法
            List<String> tmp = new ArrayList<>();
            for(int i = 0; i < n; i++) {
                tmp.add(String.valueOf(path[i]));
            }
            ret.add(new ArrayList<>(tmp));
            return;
        }
        for(int col = 0; col < n; col++) {
            if(colCheck[col] == false && dig1Check[row - col + n] == false && dig2Check[row + col] == false) {
                path[row][col] = 'Q';
                colCheck[col] = dig1Check[row - col + n] = dig2Check[row + col] = true;
                dfs(row + 1);
                //回溯
                path[row][col] = '.';
                colCheck[col] = dig1Check[row - col + n] = dig2Check[row + col] = false;
            }
        }
    }
}

4、有效的数独【解数独铺垫】

. - 力扣（LeetCode）

 注：本题并非DFS算法系列题，与搜索回溯剪枝无任何关联，仅为下文困难题“解数独”做铺垫。

4.1 算法原理

核心：设置三个布尔类型的数组，分别检查行、列、方格，哪个位置有数字，就把对应数组上的位置置为true。【类似哈希表的策略 --> 空间换取时间】

  • 判断哪行中哪个数字被使用：boolean[9][10] row;
  • 判断哪列中哪个数字被使用：boolean[9][10] col;
  • 判断哪个小方格中哪个数字被使用：boolean[3][3][10] grid;//行、列为什么设置为3，下图已给出解释

4.2 算法代码

class Solution {
    boolean[][] colCheck;// 列
    boolean[][] rowCheck;// 行
    boolean[][][] grid;

    public boolean isValidSudoku(char[][] board) {
        colCheck = new boolean[9][10];
        rowCheck = new boolean[9][10];
        grid = new boolean[3][3][10];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    //判断是否有效
                    int val = board[i][j] - '0';
                    int row = i / 3;
                    int col = j / 3;
                    if (rowCheck[i][val] || colCheck[j][val] || grid[row][col][val]) {
                        return false;
                    }
                    rowCheck[i][val] = colCheck[j][val] = grid[row][col][val] = true;
                }
            }
        }
        return true;
    }
}

5、解数独【困难】★★★

. - 力扣（LeetCode）

5.1 算法原理

首先，放入数据时需要用到上题判断有效数独的思想：

  1. 检测某一位置是否可放入某一数据：
  2. boolean[9][10] row;//行
  3. boolean[9][10] col;//列
  4. boolean[3][3][10] grip;//小方格

接着，遍历整个二维数组board，在数组数值为 '.' 的位置替换为1~9的有效字符，接着dfs下一个数值 '.' 的位置，再次替换....直至对整个数组完成对 '.' 的替换。

注意：

  • 因为输入数独仅有一个解，故一种填充方式存在错误情况，故我们应将dfs函数的返回值设置为boolean类型，当发现填充错误返回false，并进行回溯的恢复现场操作，再去寻找另一个有效的数据进行填充。
  • 我们也不需要对dfs传入指定位置的相关参数，因为我们可以按顺序一个位置一位置的去填充，填充完一个位置就去dfs下一个位置继续填充，如果1~9数字都不可以填充，则进行回溯操作将上个位置恢复现场，寻找下个可以填充的数字。

5.2 算法代码 

class Solution {
    boolean[][] rowCheck;//行
    boolean[][] colCheck;//列
    boolean[][][] grip;//小方格 

    public void solveSudoku(char[][] board) {
        rowCheck = new boolean[9][10];
        colCheck = new boolean[9][10];
        grip = new boolean[3][3][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    rowCheck[i][num] = colCheck[j][num] = grip[i / 3][j / 3][num] = true;
                }
            }
        }
        dfs(board);
    }

    public boolean dfs(char[][] board) {

        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == '.') {
                    //填数
                    for (int val = 1; val <= 9; val++) {
                        //剪枝
                        if (!rowCheck[row][val] && !colCheck[col][val] && !grip[row / 3][col / 3][val]) {
                            board[row][col] = (char)('0' + val);//要强转的数字要加小括号
                            rowCheck[row][val] = colCheck[col][val] = grip[row / 3][col / 3][val] = true;
                            boolean check = dfs(board);
                            if(!check) {
                                //不满足条件 --> 回溯
                                board[row][col] ='.';
                                rowCheck[row][val] = colCheck[col][val] = grip[row / 3][col / 3][val] = false;
                            }else {
                                return true;
                            }
                        }
                    }
                    //1~9均不可填充
                    return false;
                }
            }
        }
        //此时表格已全部填满
        return true;
    }
}

6、单词搜索

. - 力扣（LeetCode）

6.1 算法原理

  1. 遍历数组，先找到字符串的第一个元素在矩阵中的位置(x,y)
  2. 再dfs剩下的字符，从(x,y)位置的上下左右寻找，
  3. 如果找到就继续dfs下一个字符，如果找不到就return false；

细节问题：

  • 不能找已经找过的重复字符 --> 定义一个boolean数组
  • 找当前字符的上下左右位置 --> 定义两个数组:int[]dx,int[] dy
  • dx {1, -1, 0, 0}；//x+1、x-1、x、x ，当前位置横坐标的上下左右位置
  • dy {0, 0, -1, 1};  //y、y、y-1、y+1 ，当前位置纵坐标的上下左右位置

 6.2 算法代码

class Solution {
    boolean[][] visit;
    int row;
    int col;
    int[] dx;
    int[] dy;

    public boolean exist(char[][] board, String s) {
        row = board.length;
        col = board[0].length;
        visit = new boolean[row][col];
        dx = new int[] { -1, 1, 0, 0 };// x坐标 -> 上下左右
        dy = new int[] { 0, 0, -1, 1 };// y坐标 -> 上下左右
        boolean ret = false;
        //找第一个字符
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == s.charAt(0)) {
                    visit[i][j] = true;
                    if(dfs(board, i, j, s, 1)) {
                        return true;
                    }
                    //回溯
                    visit[i][j] = false;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, int i, int j, String s, int pos) {
        if (pos == s.length())
            return true;
        for(int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < row && y >= 0 && y < col && !visit[x][y] && board[x][y] == s.charAt(pos)) {
                visit[i + dx[k]][j + dy[k]] = true;
                if(dfs(board, x, y, s, pos + 1)) return true;
                //回溯
                visit[i + dx[k]][j + dy[k]] = false;
            }
        }
        //上下左右位置都没有该字符
        return false;
    }
}

7、黄金矿工

. - 力扣（LeetCode）

7.1 算法原理

本题框架与上题类似。 

  1. 遍历矩阵，寻找矿工的入口(非0位置)
  2. 接着dfs下一个位置，每进入一个位置都要记录路径和。
  3. 遍历所有入口点，选出值最大的路径和
  4. 剪枝：①：不能进入经过的位置 --> boolean[] check;
  5. 剪枝：②：只能进入原位置的上下左右位置  --> int[]dx,int[] dy

7.2 算法代码

class Solution {
    int max;//最大黄金数目
    int row, col;
    boolean[][] check;//判断是否重复进入金矿
    int[][] grid;
    int[] dx, dy;//上下左右
    public int getMaximumGold(int[][] grid_) {
        grid = grid_;
        row = grid.length;
        col = grid[0].length;
        check = new boolean[row][col];
        dx = new int[]{1, -1,0 ,0};
        dy = new int[]{0, 0, -1, 1};
        int sum = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] != 0) {
                    check[i][j] = true;
                    sum += grid[i][j];
                    dfs(i, j, sum);
                    //回溯
                    check[i][j] = false;
                    sum -= grid[i][j];
                }
            }
        }
        return max;
    }
    public void dfs(int x, int y, int sum) {
        max = Math.max(max, sum);
        for(int k = 0; k < 4; k++) {
            int n = x + dx[k];
            int m = y + dy[k];
           if(n >= 0 && n < row && m >= 0 && m < col && !check[n][m] && grid[n][m] != 0) {
                sum += grid[n][m];
                check[n][m] = true;
                dfs(n, m, sum);
                //回溯
                check[n][m] = false;
                sum -= grid[n][m];
           }
        }
    }
}

 8、不同路径 III【困难】★★★

8.1 算法原理

若本题可使用动态规划求解，但难度严重超标，将上升到竞赛级别。但本专题的DFS算法依然可以完美穷举解题。

本题思想很简单，看重代码能力：

  • 暴力dfs穷举
  • 记录矩阵中0的个数count
  • dfs穷举入口1处的所有到2的路径，记录一条完整路径中0的个数，若其中0的个数和count相同，则为正确路径；

8.2 算法代码

class Solution {
    int[] dx;
    int[] dy;
    boolean[][] check;
    int m, n;
    int ret;
    int count;//0的个数
    public int uniquePathsIII(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        int inX = 0;
        int inY = 0;
        check = new boolean[m][n];
        dx = new int[]{-1, 1, 0, 0};
        dy = new int[]{0, 0, -1, 1};
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 0) count++;
                if(grid[i][j] == 1) {
                    inX = i;
                    inY = j;
                }
            }
        check[inX][inY] = true;
        dfs(grid, inX, inY, 0);
        return ret;
    }
    public void dfs(int[][] grid, int i, int j, int count0) {
        if(grid[i][j] == 2) {
            if(count0 == count) ret++;
            return;
        }
        //每个格子的上下左右都要穷举
        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 && grid[x][y] != -1) {
                check[x][y] = true;
                if(grid[x][y] == 0) count0++;//可能这个位置是2
                dfs(grid, x, y, count0);
                //回溯
                if(grid[x][y] == 0) count0--;
                check[x][y] = false;
            }
        }
    }
}

END


http://www.kler.cn/a/301761.html

相关文章：

  • 【实验11】卷积神经网络（2）-基于LeNet实现手写体数字识别
  • HBase压测 ycsb
  • C++创建型设计模式体现出的面向对象设计原则
  • VSCode设置
  • 详解map与multimap容器
  • 第三百二十三节 Java线程教程 - Java同步器
  • 数据库锁有哪些？什么是死锁？
  • Java开发安全及防护
  • C语言手撕归并——递归与非递归实现（附动画及源码）
  • TS axios封装
  • FinOps原则：云计算成本管理的关键
  • Chainlit集成Langchain并使用通义千问实现和数据库交互的网页对话应用增强扩展（text2sql）
  • 高教社杯数模竞赛特辑论文篇-2015年D题：众筹筑屋规划方案设计
  • AI教你学Python 第1天：Python简介与环境配置
  • Python和MATLAB及C++信噪比导图(算法模型)
  • 解开密码锁的最少次数
  • cesium.js 入门到精通(1)
  • 高级java每日一道面试题-2024年9月08日-前端篇-JS的执行顺序是什么样的?
  • php实现kafka
  • 一篇文章，讲清SQL的 joins 语法
  • Java贪心算法每日一题——179.最大数
  • 【QT】Qt窗口
  • Pr：序列设置 - VR 视频
  • 【区块链 + 基层治理】社区防疫管理平台 | FISCO BCOS应用案例
  • 404 error when doing workload anlysis using locust on OpenAI API (GPT.35)
  • 【深度学习 Pytorch】深入浅出：使用PyTorch进行模型训练与GPU加速