zj

前言

今天是学习回溯算法的第五天，我们继续来一起学习回溯算法蕴含的逻辑处理，希望博主记录的内容能够对大家有所帮助，一起加油吧朋友们！💪💪💪

重新安排行程

LeetCode题目链接

这道题给一个航线列表，其中每个航线相当于一张机票从这个地点到那个地点，现在就是机票的起始机场JFK确定了，要你在所有行程中选出机场名的字典排序最小的行程（每个机票用且只能用一次）🤔

1729060434986

我们来思路梳理

问题给出的航线可以看作图的边，机场是图的顶点。我们需要从 “JFK” 出发，找出一条遍历所有航线的路径，并确保路径是按字典序最小的🤔🤔🤔 将航线列表视作有向图的边，构建邻接表表示图，且每个节点的相邻节点按字典序排序，方便后续按顺序遍历🤔从 “JFK” 开始进行深度优先搜索，优先访问字典序最小的机场。每次访问过一条航线后，将其移除，确保每条航线只用一次🤔 DFS 完成后，将访问过的节点逆序记录，因为我们在回溯过程中先完成的路径会被最后添加🤔

我们进一步来梳理回溯三要素

确定递归函数的参数和返回值

//graph: 使用邻接表存储航线图，其中每个机场对应的目的地按照字典序排序
//itinerary: 存储当前路径的列表
//airport: 当前访问的机场，作为DFS的起点
//不需要返回值，最终结果会存在于 itinerary 中

Map<String, PriorityQueue<String>> graph = new HashMap<>();//键为出发机场，值为按字典序排列的目的地队列
List<String> itinerary = new LinkedList<>();//存储最终的行程
private void backtracking(String airport){}//回溯函数（递归遍历图访问所有目的地）

回溯终止条件

1	itinerary.add(airport);//当没有更多的航线可以访问时，记录当前机场到最终的行程中

单层搜索逻辑（在每层搜索时，从当前机场出发，优先按字典序遍历所有可能的目的地。DFS会优先递归到字典序较小的路径，保证路径的最小字典序🤔 在递归访问过某个目的地后，立即将该航线从图中移除，确保不会重复使用🤔）

while (graph.containsKey(airport) && !graph.get(airport).isEmpty()) {
    String nextAirport = graph.get(airport).poll();// 递归地选择字典序最小的下一步
    backtracking(nextAirport);// 递归进入下一步，继续探索
}
itinerary.add(airport);// 回溯到此处，将路径记录下来

完整的回溯代码如下

class Solution {
    Map<String, PriorityQueue<String>> graph = new HashMap<>();
    List<String> itinerary = new LinkedList<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        //构建图,使用优先队列（最小堆）来保证目的地按字典序排序
        for(List<String> ticket : tickets){
            String from = ticket.get(0);
            String to = ticket.get(1);
            graph.putIfAbsent(from, new PriorityQueue<>());
            graph.get(from).offer(to);
        }

        //从JFK机场开始回溯搜索行程
        backtracking("JFK");

        Collections.reverse(itinerary);
        return itinerary;
    }

    private void backtracking(String airport){
        while(graph.containsKey(airport) && !graph.get(airport).isEmpty()){
            String nextAirport = graph.get(airport).poll();
            backtracking(nextAirport);//递归访问下一机场
        }
        itinerary.add(airport);//当没有更多的航线可以访问时，记录当前机场到最终的行程中
    }
}

难以理解的部分
- 首先这个优先队列的使用就是说一个机场当它有多个可达地我们把这多个可达地的字符串按字典顺序排列，优先队列会自动保证字典顺序最小的机场在前，那我们递归遍历图路径的时候就是优先得到字典顺序最小的路径🤔
- 这里的回溯部分不是很明显，这里回溯的体现是当我们递归进入一个机场时，我们poll出字典序最小的目的地，然后目的地就被移除了因为我们要保证每条航线只使用一次。这其实是回溯的一个特性：逐步探索，且不走回头路🤔当我们完成某一条路径的探索后，我们并不会马上返回之前的状态，而是通过递归继续探索其他分支。当所有递归结束后，才会回溯🤔
- 这里递归时直接poll不会影响其他递归分支的正确性。原因是：poll() 的操作是在当前递归层中发生的，它意味着我们在探索某条特定的路径，并移除该路径。当这条路径结束后，我们不会返回到之前的路径再进行探索，而是直接处理其他分支。这就是回溯的核心：当某条路径探索完成后，不会回到之前的状态🤔

N皇后

LeetCode题目链接

经典问题n皇后啊，这道题就是经典中的经典哈哈，这道题的问题就是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击

1729064817095

我们来思路梳理

我们通过递归在每一行放置皇后，确保在当前行放置皇后后，检查它是否与之前放置的皇后冲突（同一列或对角线）。如果不冲突，则继续递归放置下一行的皇后🤔如果在某一行找不到合适的位置，则进行回溯，撤销之前的操作，尝试其他可能的位置🤔当所有皇后都成功放置（即递归到最后一行时），将当前的棋盘方案加入结果集中🤔

我们来梳理回溯三要素

确定递归函数的参数和返回值

//n: 棋盘的大小，n×n 的棋盘
//row: 当前正在处理的行号
//columns: 用于记录哪些列已经放置了皇后（防止同列冲突）
//diagonals1: 用于记录哪些左上到右下方向的斜线已经放置了皇后（防止左对角线冲突）
//diagonals2: 用于记录哪些右上到左下方向的斜线已经放置了皇后（防止右对角线冲突）
//result: 存储所有可能的解法
//不需要返回值，最终的结果会存入 result 列表中
private void backtracking(int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2, char[][] board, List<List<String>> result){}

回溯终止条件

//当所有的皇后都放置完毕（即递归到最后一行时），将当前棋盘方案加入结果集
if(row == n){
    result.add(constructBoard(board));//将当前棋盘的布局加入结果集
    return;
}
//把棋盘的布局转换为字符串列表
private List<String> constructBoard(char[][] board){
    List<String> boardConfig = new ArrayList<>();
    for(char[] row : board){
        boardConfig.add(new String(row));
    }
    return boardConfig;
}

单层搜索过程（在当前行 row，依次尝试在每一列放置皇后🤔 每次放置时，需要检查该列以及两个对角线上是否有皇后🤔 如果安全，将该位置标记为已放置皇后，并递归放置下一行的皇后🤔当回溯时，撤销上一步的操作，继续尝试其他可能的放置🤔）

//尝试在每一列放置皇后
for(int col = 0; col < n; col++){
    //检查安全性
    if(columns.contains(col) || diagonals1.contains(row - col) || diagonals2.contains(row + col)){
        continue;//发生冲突跳过该位置
    }
    
    //放置皇后
    board[row][col] = 'Q';
    columns.add(col);
    diagonals1.add(row - col);
    diagonals2.add(row + col);
    
    //递归往下一行放置皇后
    backtracking(n, row + 1, columns, diagonals1, diagonals2, board, result);
    
    //回溯
    board[row][col] = '.';
    columns.remove(col);
    diagonals1.remove(row - col);
    diagonals2.remove(row + col);
}

回溯的完整代码如下

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();//结果集
        Set<Integer> columns = new HashSet<>();//记录已经放置皇后的列
        Set<Integer> diagonals1 = new HashSet<>();//记录左上到右下对角线冲突情况
        Set<Integer> diagonals2 = new HashSet<>();//记录右上到左下对角线冲突情况
        //初始化棋盘
        char[][] board = new char[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                board[i][j] = '.';
            }
        }
        backtracking(n, 0, columns, diagonals1, diagonals2, board, result);
        return result;
    }

    private void backtracking(int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2, char[][] board, List<List<String>> result){
        //终止条件
        if(row == n){
            result.add(constructBoard(board));
        }

        //尝试在每一列放置皇后
    for(int col = 0; col < n; col++){
        //检查安全性
        if(columns.contains(col) || diagonals1.contains(row - col) || diagonals2.contains(row + col)){
            continue;//发生冲突跳过该位置
        }
        
        //放置皇后
        board[row][col] = 'Q';
        columns.add(col);
        diagonals1.add(row - col);
        diagonals2.add(row + col);
        
        //递归往下一行放置皇后
        backtracking(n, row + 1, columns, diagonals1, diagonals2, board, result);
        
        //回溯
        board[row][col] = '.';
        columns.remove(col);
        diagonals1.remove(row - col);
        diagonals2.remove(row + col);
    }
}

    //把棋盘的布局转换为字符串列表
    private List<String> constructBoard(char[][] board){
        List<String> boardConfig = new ArrayList<>();
        for(char[] row : board){
            boardConfig.add(new String(row));
        }
        return boardConfig;
    }
}

难以理解的部分
- 这里的回溯函数的参数实际上是可以把棋盘board、列columns、两个对角线标记(diagonals1和diagonals2)以及结果集(result)作为全局变量🤔，不用太过纠结
- 对于右上到左下的对角线，它们的行号与列号之和是相同的。因此用 row + col 可以唯一标识棋盘上的这一对角线🤔同样对于左上到右下方向的对角线，它们的行号与列号之差是相同的。因此用 row - col 可以唯一标识棋盘上的主对角线🤔

1729068788705

1729068982000

解数独

LeetCode题目链接

就是给一个二维字符数组作为数独题，通过修改其中的’.’来填数独字，数独的解法规则

数字1-9在每行每列只能出现一次
数字1-9在每个3x3小方块里只能出现一次

1729069835254

我们来梳理思路

逐个遍历棋盘上的空格（用 '.' 表示），对每一个空格依次尝试填入数字 1-9🤔 对于每个填入的数字，需要检查该数字在当前行、列、以及 3x3 小方块内是否已经存在🤔 如果某个数字放置成功，递归继续处理下一个空格。如果某个数字导致后续位置无法继续合法填入数字，则回退到上一步，尝试其他数字🤔当所有空格都成功填入合法的数字时，数独解答完成

我们进一步来梳理回溯三要素

确定递归函数的参数和返回值

1
2
3

//board: 当前的数独棋盘，是一个二维字符数组，表示数独的当前状态
//递归函数不需要返回值，最终数独解会直接修改 board 数组
private boolean backtrack(char[][] board) {}

回溯终止条件

//当所有空格都被填满时（即递归遍历完所有格子），解法完成
//如果能够顺利填充所有格子，数独就是有解的
for(循环条件){
    填充处理
    return false;
}
return true;//所有格子成功填充

单层搜索过程

for (char num = '1'; num <= '9'; num++) {
    if (isValid(board, row, col, num)) {// 如果当前数字放置在该格子是合法的
        board[row][col] = num;
        // 递归处理下一个格子
        if (backtrack(board)) {
            return true;  // 如果成功解开数独，返回 true
        }
        board[row][col] = '.';// 回溯
    }
}
return false;

//检查合法性
private boolean isValid(char[][] board, int row, int col, char num) {
	//检查行重复
    for (int i = 0; i < 9; i++) {
        if (board[row][i] == num) {
            return false;
        }
    }
    //检查列重复
    for (int i = 0; i < 9; i++) {
        if (board[i][col] == num) {
            return false;
        }
    }
    //检查3x3方格块重复
    int startRow = (row / 3) * 3;
    int startCol = (col / 3) * 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[startRow + i][startCol + j] == num) {
                return false;
            }
        }
    }
    
    return true;
}

完整代码如下

class Solution {
    public void solveSudoku(char[][] board) {
        backtracking(board);
    }

    private boolean backtracking(char[][] board){
        //遍历每个格子
        for(int row = 0; row < 9; row++){
            for(int col = 0; col < 9; col++){
                if(board[row][col] != '.')continue;//跳过已有数字的格子

                //填数
                for(char num = '1'; num <= '9'; num++){
                    if(isValid(board, row, col, num)){
                        board[row][col] = num;
                        if(backtracking(board))return true;//递归往下处理并成功解开数独
                        board[row][col]='.';//没解开则回溯
                    }
                }
                return false;//填1-9不行则回溯
            }
        }
        return true;//都成功填充
    }
    //检查合法性
    private boolean isValid(char[][] board, int row, int col, char num){
        //检查行重复
        for(int i = 0; i < 9; i++){
            if(board[row][i] == num) return false;
        }
        //检查列重复
        for(int i = 0; i < 9; i++){
            if(board[i][col] == num)return false;
        }
        //检查3x3小方格是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if(board[startRow + i][startCol + j] == num)return false;
            }
        }
        return true;
    }
}

总结

今天对回溯中经典的数独、N皇后以及一道行程安排题进行学习，这几道题都蛮硬的，大家可以多啃几遍，明天开始贪心算法的学习，大家一起加油✊✊✊

前言

重新安排行程

N皇后

解数独

总结

Copyright © 2020 | Author: 周建 | Theme By Coder