• 力扣刷题day26|332重新安排行程、51.N皇后、37解数独

    文章目录

    332. 重新安排行程

    力扣题目链接

    给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

    所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

    • 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

    假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

    示例 1：

    输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

    • 1
    • 2

    示例 2：

    输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

    • 1
    • 2
    • 3

    思路

    首先找到JFK机场，再记录JFK的能到达的机场，在记录其他机场能到的机场，然后再找到一条条路，走不下去就回溯

    难点：记录映射关系

    字母序靠前排在前面，如何该记录映射关系呢 ？

    首先是一个机场映射多个机场，在map里就是一个key对应多个value，其中value是一个集合，里面可能包含很多值。

    即Map> map;

    但是用List存储到达机场并不方便，因为要删除元素，为什么一定要增删元素呢，正如开篇我给出的图中所示，出发机场和到达机场是会重复的，搜索的过程没及时删除目的机场就会死循环。

    所以搜索的过程中就是要不断的删List里的元素，那么推荐使用Map> map：Map<出发机场, map<到达机场, 航班次数>> map

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

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

    相当于说我不删，我就做一个标记！

    回溯三部曲
    1. 递归函数参数

    定义Map> map为全局变量

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

    List<String> res = new ArrayList<>();
Map<String, Map<String, Integer>> map;
boolean backtracking(int ticketNum) {

    • 1
    • 2
    • 3

    注：注意函数返回值用的是bool！

    因为我们只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线，所以找到了这个叶子节点了直接返回

    1. 递归终止条件

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

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

    本题的result就是记录路径的（就一条），在如下单层搜索的逻辑中result就添加元素了。

    if (res.size() == ticketNum + 1) {
    return true;
}

    • 1
    • 2
    • 3
    1. 单层搜索的逻辑

    回溯的过程中，如何遍历一个机场所对应的所有机场呢？

    选择Map> map来做机场之间的映射。

    使用Map.Entry遍历Map

    // 单层
String last = res.getLast();
if(map.containsKey(last)) {
    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;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

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

    完整代码

        public List<String> findItinerary(List<List<String>> tickets) {
        // 把所有票加进map里
        for (List<String> t : tickets) {
            Map<String, Integer> temp;
            // 如果map里有这个出发地
            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<>();
                temp.put(t.get(1), 1);
            }
            map.put(t.get(0), temp);
        }

        res.add("JFK");
        backtracking(tickets.size());
        return new ArrayList<>(res);
    }
    Deque<String> res = new ArrayDeque<>();
//    LinkedList res = new LinkedList<>();
    Map<String, Map<String, Integer>> map = new HashMap<String, Map<String, Integer>>();;
    boolean backtracking(int ticketNum) {
        if (res.size() == ticketNum + 1) {
            return true;
        }

        // 单层
        String last = res.getLast();
        if(map.containsKey(last)) {
            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;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    51. N皇后

    力扣题目链接

    按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

    n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

    给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

    每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

    示例 1：

    输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

    • 1
    • 2
    • 3

    示例 2：

    输入：n = 1
输出：[["Q"]]

    • 1
    • 2

    思路

    皇后们的约束条件：

    1. 不能同行
    2. 不能同列
    3. 不能同斜线

    二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度。

    那么我们用皇后们的约束条件，来回溯搜索这棵树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。

    回溯三部曲
    1. 递归函数参数

    定义全局变量res来记录最终结果。

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

    List<List<String>> res = new ArrayList<>();
void backtracking(int n, int row, char[][] chessboard) {

    • 1
    • 2
    1. 递归终止条件

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

    if (row == n) {
    // 将char数组转化为String
    List<String> list = new ArrayList<>();
    for (char[] chars : chessboard) {
        list.add(new String(chars));
    }
    res.add(new ArrayList<>(list));
    return;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    1. 单层搜索的逻辑

    递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。

    每次都是要从新的一行的起始位置开始搜，所以都是从0开始。

    // 单层
for (int col = 0; col < n; col++) {
    if (isValid(n, row, col, chessboard)) { // 如果合法就可以放
        chessboard[row][col] = 'Q'; // 放皇后
        backtracking(n, row + 1, chessboard);
        chessboard[row][col] = '.'; // 回溯将皇后替换为空格
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    验证棋盘是否合法

    按照如下标准去重：

    1. 不能同行
    2. 不能同列
    3. 不能同斜线 （左上到右下45度角和左下到右上45度角）
    // 判断皇后是否能在该位置放置
boolean isValid(int n, int row, int col, 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;
        }
    }
    // 检查左下到右上45度角是否有皇后
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    为什么不用判断行呢？

    判断当前位置是否有效，只判断列不判断行，是因为当前i位置的前面肯定全是空格，如果有皇后的话，在之前皇后的位置就往下一层row遍历了

    完整代码

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

List<List<String>> res = new ArrayList<>();
void backtracking(int n, int row, char[][] chessboard) {
    if (row == n) {
        // 将char数组转化为String
        List<String> list = new ArrayList<>();
        for (char[] chars : chessboard) {
            list.add(new String(chars));
        }
        res.add(new ArrayList<>(list));
        return;
    }

    // 单层
    for (int col = 0; col < n; col++) {
        if (isValid(n, row, col, chessboard)) { // 如果合法就可以放
            chessboard[row][col] = 'Q'; // 放皇后
            backtracking(n, row + 1, chessboard);
            chessboard[row][col] = '.'; // 回溯将皇后替换为空格
        }
    }
}

// 判断皇后是否能在该位置放置
boolean isValid(int n, int row, int col, 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;
        }
    }
    // 检查左下到右上45度角是否有皇后
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    51. N皇后

    力扣题目链接

    按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

    n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

    给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

    每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

    示例 1：

    输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

    • 1
    • 2
    • 3

    示例 2：

    输入：n = 1
输出：[["Q"]]

    • 1
    • 2

    思路

    皇后们的约束条件：

    1. 不能同行
    2. 不能同列
    3. 不能同斜线

    二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度。

    那么我们用皇后们的约束条件，来回溯搜索这棵树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。

    回溯三部曲
    1. 递归函数参数

    定义全局变量res来记录最终结果。

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

    List<List<String>> res = new ArrayList<>();
void backtracking(int n, int row, char[][] chessboard) {

    • 1
    • 2
    1. 递归终止条件

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

    if (row == n) {
    // 将char数组转化为String
    List<String> list = new ArrayList<>();
    for (char[] chars : chessboard) {
        list.add(new String(chars));
    }
    res.add(new ArrayList<>(list));
    return;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    1. 单层搜索的逻辑

    递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。

    每次都是要从新的一行的起始位置开始搜，所以都是从0开始。

    // 单层
for (int col = 0; col < n; col++) {
    if (isValid(n, row, col, chessboard)) { // 如果合法就可以放
        chessboard[row][col] = 'Q'; // 放皇后
        backtracking(n, row + 1, chessboard);
        chessboard[row][col] = '.'; // 回溯将皇后替换为空格
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    验证棋盘是否合法

    按照如下标准去重：

    1. 不能同行
    2. 不能同列
    3. 不能同斜线 （左上到右下45度角和左下到右上45度角）
    // 判断皇后是否能在该位置放置
boolean isValid(int n, int row, int col, 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;
        }
    }
    // 检查左下到右上45度角是否有皇后
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    为什么不用判断行呢？

    判断当前位置是否有效，只判断列不判断行，是因为当前i位置的前面肯定全是空格，如果有皇后的话，在之前皇后的位置就往下一层row遍历了

    完整代码

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

List<List<String>> res = new ArrayList<>();
void backtracking(int n, int row, char[][] chessboard) {
    if (row == n) {
        // 将char数组转化为String
        List<String> list = new ArrayList<>();
        for (char[] chars : chessboard) {
            list.add(new String(chars));
        }
        res.add(new ArrayList<>(list));
        return;
    }

    // 单层
    for (int col = 0; col < n; col++) {
        if (isValid(n, row, col, chessboard)) { // 如果合法就可以放
            chessboard[row][col] = 'Q'; // 放皇后
            backtracking(n, row + 1, chessboard);
            chessboard[row][col] = '.'; // 回溯将皇后替换为空格
        }
    }
}

// 判断皇后是否能在该位置放置
boolean isValid(int n, int row, int col, 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;
        }
    }
    // 检查左下到右上45度角是否有皇后
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
  • 相关阅读:
    ICV报告: ADAS SoC市场规模将在2024年迎来较大突破
    网格搜索和交叉验证
    Elasticsearch in 查询
    JAVA基于J2ME的手机游戏开发免费
    shell bash中设置命令set
    LeetCode：2. 两数之和
    集美大学 - 2840 - 实验4-1
    七天.NET 8操作SQLite入门到实战 - SQLite 简介
    高纯PFA容量瓶PFA试剂瓶在半导体材料的应用
    linux设备模型：pci驱动程序注册过程
  • 原文地址：https://blog.csdn.net/dtc1261/article/details/127455119