算法打卡day26|回溯法篇06|Leetcode 332.重新安排行程、51. N皇后、37. 解数独

2024-03-28 15:32:07
开发
19

算法题

Leetcode 332.重新安排行程

个人思路

是使用回溯法，但怎么用是个问题...

解法

对于死循环，例子如下；出发机场和到达机场也会重复的，如果在解题的过程中没有对集合元素处理好，就会死循环。

记录映射关系；一个机场映射多个机场，机场之间要靠字母序排列，一个机场映射多个机场，可以使用Map，Map<String, Map<String, Integer>> map

在遍历map<出发机场, map<到达机场, 航班次数>> targets的过程中，可以使用"航班次数"这个字段的数字做相应的增减，来标记到达机场是否使用过了。

如果“航班次数”大于零，说明目的地还可以飞，如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。相当于说不删，就做一个标记。

回溯法

本题以输入：[["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]为例，抽象为树形结构如下：

回溯法三部曲

1.递归函数参数

结果列表res 和记录映射的map

参数里需要ticketNum，表示有多少个航班（终止条件会用上）。

注意函数返回值用的是bool！因为只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线，所以找到了这个叶子节点了直接返回

2.递归终止条件

拿题目中的示例为例，输入: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] ，这是有4个航班，那么只要找出一种行程，行程里的机场个数是5就可以了。

所以终止条件是：回溯遍历的过程中，遇到的机场个数，如果达到了（航班数量+1），那么就找到了一个行程，把所有航班串在一起了。

3.单层搜索的逻辑

通过Map<String, Map<String, Integer>> map里的Integer字段来判断这个集合里的机场是否使用过，这样避免了直接去删元素。

class Solution {
    private Deque<String> res;//存储结果
    private Map<String, Map<String, Integer>> map;

    public List<String> findItinerary(List<List<String>> tickets) {
        map = new HashMap<String, Map<String, Integer>>();//初始化
        res = new LinkedList<>();

        for(List<String> t : tickets){
            Map<String, Integer> temp;

            if(map.containsKey(t.get(0))){
                temp = map.get(t.get(0));
                temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
            }else{
                temp = new TreeMap<>();//升序Map
                temp.put(t.get(1), 1);
            }
            map.put(t.get(0), temp);

        }
        res.add("JFK");//出发地
        backTracking(tickets.size());
        return new ArrayList<>(res);
    }

    private boolean backTracking(int ticketNum){//递归
        if(res.size() == ticketNum + 1){//终止条件
            return true;
        }

        String last = res.getLast();
        if(map.containsKey(last)){//防止出现null
            for(Map.Entry<String, Integer> target : map.get(last).entrySet()){
                int count = target.getValue();
                if(count > 0){
                    res.add(target.getKey());
                    target.setValue(count - 1);//防止出现死循环
                    if(backTracking(ticketNum)) return true;
                    res.removeLast();//回溯
                    target.setValue(count);
                }
            }
        }
        return false;
    }
}

时间复杂度:O(n*m)；（每个航班数*每个航班都可能被尝试）

空间复杂度:O(n*m);（当前路线*调用栈）

Leetcode 51. N皇后

题目链接:51. N皇后

大佬视频讲解：N皇后视频讲解

个人思路

回溯法中最经典的一题，也是非常的难，注意皇后的条件，递归遍历回溯找到结果。

解法

回溯法

皇后们的约束条件：

不能同行
不能同列
不能同斜线

搜索皇后的位置，可以抽象为一棵树

如上，二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度。那么用皇后们的约束条件，来回溯搜索这棵树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。

回溯法三部曲

1.递归函数参数

定义全局变量二维数组result来记录最终结果。

参数n是棋盘的大小，然后用row来记录当前遍历到棋盘的第几层了。

2.递归终止条件

当递归到棋盘最底层（也就是叶子节点）的时候，就可以收集结果并返回了。

3.单层搜索的逻辑

递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。每次都是要从新的一行的起始位置开始搜，所以都是从0开始。

验证棋盘是否合法

按照皇后的标准去重

不能同行
不能同列
不能同斜线（45度和135度角）

class Solution {
    List<List<String>> res = new ArrayList<>();//结果列表

    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];
        for (char[] c : chessboard) {
            Arrays.fill(c, '.');
        }
        backTrack(n, 0, chessboard);
        return res;
    }


    public void backTrack(int n, int row, char[][] chessboard) {
        if (row == n) {//叶子节点
            res.add(Array2List(chessboard));
            return;
        }

        for (int col = 0;col < n; ++col) {
            if (isValid (row, col, n, chessboard)) {
                chessboard[row][col] = 'Q';
                backTrack(n, row+1, chessboard);
                chessboard[row][col] = '.';
            }
        }

    }


    public List Array2List(char[][] chessboard) {//处理结果
        List<String> list = new ArrayList<>();

        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }


    public boolean isValid(int row, int col, int n, char[][] chessboard) {//检查是否合法
        // 检查列
        for (int i=0; i<row; ++i) { // 相当于剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }

        // 检查45度对角线
        for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }

        // 检查135度对角线
        for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}

时间复杂度:O(n!)；（循环递归所有格子）

空间复杂度:O(n);（递归栈的深度最多为 n）

Leetcode 37. 解数独

题目链接:37. 解数独

大佬视频讲解：解数独视频讲解

个人思路

这种二维递归还是写不出来...

解法

回溯法

把解数独问题抽象为如下树形结构

本题中棋盘的每一个位置都要放一个数字（而N皇后是一行只放一个皇后），并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。

递归三部曲

1.递归函数以及参数

递归函数的返回值需要是bool类型，因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用bool返回值。

2.递归终止条件

解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回，本题递归不用终止条件，因为递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止。

3.递归单层搜索逻辑

在树形图中可以看出需要的是一个二维的递归（也就是两个for循环嵌套着递归）

一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性。如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解。那么直接返回， 这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！

判断棋盘是否合法

判断棋盘是否合法有如下三个维度：

同行是否重复
同列是否重复
9宫格里是否重复

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

    private boolean solveSudokuHelper(char[][] board){
        //一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！
 
        for (int i = 0; i < 9; i++){ // 遍历行
            for (int j = 0; j < 9; j++){ // 遍历列
                if (board[i][j] != '.'){ // 跳过原始数字
                    continue;
                }
                for (char k = '1'; k <= '9'; k++){ // (i, j) 这个位置放k是否合适
                    if (isValidSudoku(i, j, k, board)){
                        board[i][j] = k;
                        if (solveSudokuHelper(board)){ // 如果找到合适一组立刻返回
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                // 9个数都试完了，都不行，那么就返回false
                return false;
          
            }
        }
        
        return true;// 遍历完没有返回false，说明找到了合适棋盘位置了
    }
    
    //判断棋盘是否合法
    private boolean isValidSudoku(int row, int col, char val, char[][] board){
        // 同行是否重复
        for (int i = 0; i < 9; i++){
            if (board[row][i] == val){
                return false;
            }
        }
        // 同列是否重复
        for (int j = 0; j < 9; j++){
            if (board[j][col] == val){
                return false;
            }
        }
        // 9宫格里是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++){
            for (int j = startCol; j < startCol + 3; j++){
                if (board[i][j] == val){
                    return false;
                }
            }
        }
        return true;
    }
}

时间复杂度:O(9^(n/2))；（其中n是空格的数量）

空间复杂度:O(n);（递归栈的深度最多为 n）

以上是个人的思考反思与总结，若只想根据系列题刷，参考卡哥的网址代码随想录算法官网

原文地址:https://blog.csdn.net/unstoppableyi/article/details/136945251 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1773251707904593920.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部