代码随想录算法训练营第三十天天 |332.重新安排行程，51.N皇后，37.解数独（待补充）

小灰灰 2024-04-23 04:15 11阅读 0赞

### 332.重新安排行程（待补充） ###

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ -]

2、文章讲解：[代码随想录][Link 1]

3、题目：

给定一个机票的字符串二维数组 \[from, to\]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。

提示：

*  如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 \["JFK", "LGA"\] 与 \["JFK", "LGB"\] 相比就更小，排序更靠前
 *  所有的机场都用三个大写字母表示（机场代码）。
 *  假定所有机票至少存在一种合理的行程。
 *  所有的机票必须都用一次 且 只能用一次。

示例 1：

*  输入：\[\["MUC", "LHR"\], \["JFK", "MUC"\], \["SFO", "SJC"\], \["LHR", "SFO"\]\]
 *  输出：\["JFK", "MUC", "LHR", "SFO", "SJC"\]

示例 2：

*  输入：\[\["JFK","SFO"\],\["JFK","ATL"\],\["SFO","ATL"\],\["ATL","JFK"\],\["ATL","SFO"\]\]
 *  输出：\["JFK","ATL","JFK","SFO","ATL","SFO"\]
 *  解释：另一种有效的行程是 \["JFK","SFO","ATL","JFK","ATL","SFO"\]。但是它自然排序更大更靠后。

class Solution {
        private Deque<String> res;
        private Map<String, Map<String, Integer>> map;
    
        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;
        }
    
        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);
        }
    }

### 51.N皇后 ###

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 1]

2、文章讲解：[代码随想录][Link 2]

3、题目：

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

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

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

示例 1：

![a58db05eb3a139c4db3a0e8e77efbc64.png][]

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

示例 2：

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

4、视频链接：

[这就是传说中的N皇后？ 回溯算法安排！| LeetCode：51.N皇后\_哔哩哔哩\_bilibili][N_ _ LeetCode_51.N_bilibili]

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;
        }
    }

### 37.解数独 ###

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 2]

2、文章讲解：[代码随想录][Link 3]

3、题目：

编写一个程序，通过填充空格来解决数独问题。

一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。

![798db4d49e581d38cec56608677f9940.png][]

一个数独。

![fcc712961544c66420364feb3e8162bc.png][]

答案被标成红色。

提示：

*  给定的数独序列只包含数字 1-9 和字符 '.' 。
 *  你可以假设给定的数独只有唯一解。
 *  给定数独永远是 9x9 形式的。

4、视频链接：

[回溯算法二维递归？解数独不过如此！| LeetCode：37. 解数独\_哔哩哔哩\_bilibili][LeetCode_37. _bilibili]

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;
                    // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
                    // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
                }
            }
            // 遍历完没有返回false，说明找到了合适棋盘位置了
            return true;
        }
    
        /**
         * 判断棋盘是否合法有如下三个维度:
         * 同行是否重复
         * 同列是否重复
         * 9宫格里是否重复
         */
        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;
        }
    }

### 总结：（待补充） ###

[LeetCode_ -]: https://leetcode.cn/problems/reconstruct-itinerary/
[Link 1]: https://www.programmercarl.com/0332.%E9%87%8D%E6%96%B0%E5%AE%89%E6%8E%92%E8%A1%8C%E7%A8%8B.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode_ - 1]: https://leetcode.cn/problems/n-queens/
[Link 2]: https://www.programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[a58db05eb3a139c4db3a0e8e77efbc64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/8a61bb55691e4bf0acdee1fce5bc943e.png
[N_ _ LeetCode_51.N_bilibili]: https://www.bilibili.com/video/BV1Rd4y1c7Bq/
[LeetCode_ - 2]: https://leetcode.cn/problems/sudoku-solver/
[Link 3]: https://www.programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[798db4d49e581d38cec56608677f9940.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/1c0522e326df4222b84b02b4ba4d4214.png
[fcc712961544c66420364feb3e8162bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/9d3130165d7f481a927a8683b1a9aaaa.png
[LeetCode_37. _bilibili]: https://www.bilibili.com/video/BV1TW4y1471V/