算法训练Day30|● 332.重新安排行程 ● 51. N皇后 ● 37. 解数独

 1class Solution {
 2
 3    LinkedList<String> res; // 存放结果
 4    LinkedList<String> path = new LinkedList<>();  // 存放路径
 5
 6    public List<String> findItinerary(List<List<String>> tickets) {
 7        Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1))); // 将票程目的机场进行排序，
 8        path.add("JFK"); // 起始机场"JFK"
 9        boolean[] used = new boolean[tickets.size()]; //标记数组：跟踪机票是否使用
10        backtracking((ArrayList) tickets, used); // 开始回溯过程  为什么进行强转？猜测是便于对ArrayList方法的调用？
11        return res; // 返回结果
12    }
13
14    public boolean backtracking(ArrayList<List<String>> tickets, boolean[] used) {
15        if (path.size() == tickets.size() + 1) { // 一个车程tickets两个节点，2车程3个机场节点
16            res = new LinkedList(path); // 将当前路径存储为结果
17            return true; // 表示成功完成回溯
18        }
19
20        for (int i = 0; i < tickets.size(); i++) {
21            if (!used[i] && tickets.get(i).get(0).equals(path.getLast())) { // 如果机票未使用且起始机场与路径中的最后一个机场匹配
22                path.add(tickets.get(i).get(1)); // 将目的机场加入路径中
23                used[i] = true; // 标记机票已使用
24
25                if (backtracking(tickets, used)) { // 递归探索下一张机票
26                    return true; // 如果找到有效的行程，返回true
27                }
28
29                used[i] = false; // 标记机票未使用，以便其他可能的路径使用
30                path.removeLast(); // 从路径中移除最后一个机场
31            }
32        }
33        return false; // 当前路径没有找到有效的行程
34    }
35}

 1class Solution {
 2    List<List<String>> res = new ArrayList<>(); // 存储最终的结果
 3
 4    public List<List<String>> solveNQueens(int n) {
 5        char[][] chessboard = new char[n][n]; // 创建一个n*n的二维字符数组
 6        for (char[] c : chessboard) { 
 7            Arrays.fill(c, '.');
 8        }
 9        // for (int i = 0; i < chessboard.length; i++) {
10        //     for (int j = 0; j < chessboard[i].length; j++) {
11        // // 对二维数组的每个元素进行操作
12        //         chessboard[i][j] = '.';
13        // // 其他操作...
14        //     }
15        // }
16        backtracking(n, 0, chessboard);
17        return res;
18    }
19    public void backtracking(int n, int row, char[][] chessboard) {
20        if (row == n) {
21            res.add(Array2List(chessboard));
22            return;
23        }
24        for (int col = 0; col < n; col++) {
25            if (isValid(row, col, n, chessboard)) {
26                chessboard[row][col] = 'Q';
27                backtracking(n, row + 1, chessboard);
28                chessboard[row][col] = '.';
29            }
30        }
31    }
32
33    public List Array2List(char[][] chessboard) {
34        List<String> list = new ArrayList<>();
35        for (char[] c : chessboard) {
36            list.add(String.copyValueOf(c));
37        }
38        return list;
39    }
40
41    public boolean isValid(int row, int col, int n, char[][] chessboard) {
42        // 检查列
43        for (int i = 0; i < row; i++) {
44            if (chessboard[i][col] == 'Q') {
45                return false;
46            }
47        }
48        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
49            if (chessboard[i][j] == 'Q') {
50                return false;
51            }
52        }
53        // 检查135度对角线
54        for (int i = row -1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
55            if (chessboard[i][j] == 'Q') {
56                return false;
57            }
58        }
59        return false;
60    }
61}

 1class Solution {
 2
 3    public void solveSudoku(char[][] board) {
 4        solveSudokuHelper(board);
 5    }
 6
 7    // 回溯函数
 8    public boolean solveSudokuHelper(char[][] board) {
 9        for (int i = 0; i < 9; i++) { // 遍历行
10            for (int j = 0; j < 9; j++) { // 遍历列
11                if (board[i][j] != '.') { // 跳过数字
12                    continue;
13                }
14                // 为空白处赋予数字字符
15                for (char k = '1'; k <= '9'; k++) {
16                    if (isValidSudoku(i, j, k, board)) { // 判断行列是否有效
17                        board[i][j] = k; // 有效则赋值
18                        if (solveSudokuHelper(board)) { // 找到一个符合条件的结果立刻返回true
19                            return true;
20                        }
21                        board[i][j] = '.'; // 无效则回溯，剪枝操作
22                    }
23                }
24
25                return false; // 如果该节点九个数都不满足要求，返回false
26            }
27        }
28        return true; // 最后找到返回true
29    }
30
31    public boolean isValidSudoku(int row, int col, char val, char[][] board) {
32        for (int i = 0; i < 9; i++) {
33            if (board[row][i] == val) {
34                return false;
35            }
36        }
37        for (int j = 0; j < 9; j++) {
38            if (board[j][col] == val) {
39                return false;
40            }
41        }
42        // 9宫格内去重
43        int startRow = (row / 3) * 3;
44        int startCol = (col / 3) * 3;
45        for (int i = startRow; i < startRow + 3; i++) {
46            for (int j = startCol; j < startCol + 3; j++) {
47                if (board[i][j] == val) {
48                    return false;
49                }
50            }
51        }
52        return true;
53    }
54}