代码随想录算法训练营第二十六天-332重新安排行程、51N皇后、 37解数独

前言
状态：今天的题，看标注说都很难，先去总结再做这个。时间不太够了，都是直接看的解析然后做题。
更新

1 2	24-06-12 初始记录 24-06-13 完成题解

初步题解

51N 皇后

题目链接：(https://leetcode.cn/problems/n-queens)

37 解数独

题目链接：(https://leetcode.cn/problems/sudoku-solver)

看解析

332 重新安排行程

题目链接/文章讲解：(https://programmercarl.com/0332.重新安排行程.html)

解法超时（第 80 个用例）：加上剪枝不会超时。别的思路都和清晰，但是剪枝那一步有点难想到。

public static List<String> findItinerary(List<List<String>> tickets) {  
    List<String> resultOne = new ArrayList<>();  
  
    // 按字典排序排序（目的地排序）
    tickets.sort(Comparator.comparing(o -> o.get(1)));  
    // 用于记录当前节点是否使用  
    boolean[] flagList = new boolean[tickets.size()];  
  
    // 行程必须从JFK开始  
    resultOne.add("JFK");  
  
    // 这里如果找到一条就直接返回  
    findItineraryDFS(flagList, tickets, resultOne);  
    return resultOne;  
}  
  
private static boolean findItineraryDFS(boolean[] flagList, List<List<String>> tickets, List<String> resultOne) {  
    // tickets为线路数，节点数要加1  
    if (resultOne.size() == tickets.size() + 1) {  
        return true;  
    }  
  
    for (int i = 0; i < tickets.size(); i++) {  
	    // 为了防止超时加上这句的剪枝
	    // 如果这张票和上张票相同 且上张票没用过 说明是从上张票回溯过来的，已经遍历过这种情况，跳过
	    if(i > 0 && tickets.get(i).equals(tickets.get(i - 1)) && !flagList[i - 1]) continue;
	    
        if (!flagList[i] && tickets.get(i).get(0).equals(resultOne.get(resultOne.size() - 1))) {  
            resultOne.add(tickets.get(i).get(1));  
            flagList[i] = true;  
  
            if (findItineraryDFS(flagList, tickets, resultOne)) {  
                return true;  
            }  
  
            resultOne.remove(resultOne.size() - 1);  
            flagList[i] = false;  
        }  
    }  
    return false;  
}

51N 皇后

题目链接/文章讲解：(https://programmercarl.com/0051.N皇后.html)

public class LE51 {  
    public static void main(String[] args) {  
        solveNQueens(4);  
    }  
  
    public static List<List<String>> solveNQueens(int n) {  
        List<List<String>> result = new ArrayList<>();  
        char[][] chars = new char[n][n];  
  
        for (char[] c : chars) {  
            Arrays.fill(c, '.');  
        }  
  
        solveNQueensDFS(0, n, chars, result);  
        return result;  
    }  
  
    /**  
     * @param row    行数  
     * @param n      棋盘大小  
     * @param chars  棋盘摆法  
     * @param result 结果  
     */  
    private static void solveNQueensDFS(int row, int n, char[][] chars, List<List<String>> result) {  
        if (row == n) {  
            List<String> list = new ArrayList<>();  
            for (char[] aChar : chars) {  
                list.add(String.copyValueOf(aChar));  
            }  
            result.add(list);  
            return;  
        }  
  
        for (int i = 0; i < n; i++) {  
            if (isValid(row, i, n, chars)) {  
                chars[row][i] = 'Q';  
                solveNQueensDFS(row + 1, n, chars, result);  
                chars[row][i] = '.';  
            }  
        }  
    }  
  
    private static boolean isValid(int row, int col, int n, char[][] chars) {  
        // 检查列  
        for (int i = 0; i < row; ++i) {  
            if (chars[i][col] == 'Q') {  
                return false;  
            }  
        }  
  
        // 检查45度对角线  
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {  
            if (chars[i][j] == 'Q') {  
                return false;  
            }  
        }  
  
        // 检查135度对角线  
        for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {  
            if (chars[i][j] == 'Q') {  
                return false;  
            }  
        }  
        return true;  
    }  
}

37 解数独

题目链接/文章讲解：(https://programmercarl.com/0037.解数独.html)

public class LE37 {  
    public void solveSudoku(char[][] board) {  
        solveSudokuDFS(board);  
    }  
  
    private boolean solveSudokuDFS(char[][] board) {  
        for (int i = 0; i < board.length; i++) {  
            for (int j = 0; j < board[0].length; j++) {  
                if (board[i][j] != '0') {  
                    continue;  
                }  
                for (char k = '1'; k <= '9'; k++) {  
                    if (isvalid(i, j, k, board)) {  
                        board[i][j] = k;  
  
                        if (solveSudokuDFS(board)) {  
                            return true;  
                        }  
                        board[i][j] = '.';  
                    }  
                }  
                // 走到这一行，说明直到递归完毕，都没有返回true   
return false;  
            }  
  
        }  
  
        return true;  
    }  
  
    /**  
     * 判断棋盘放入这个数是否合法  
     *  
     * @param i     行  
     * @param j     列  
     * @param k     值  
     * @param board 棋盘  
     * @return 是否合法  
     */  
    private boolean isvalid(int i, int j, char k, char[][] board) {  
        // 行中是否含有这个数  
        // 列中是否含有这个数  
        for (int index = 0; index < board.length; index++) {  
            if (board[i][index] == k) {  
                return false;  
            }  
            if (board[index][j] == k) {  
                return false;  
            }  
        }  
  
        // 9宫格中是否含有这个数  
        int x = (i / 3) * 3;  
        int y = (j / 3) * 3;  
  
        for (int indexX = x; indexX < x + 3; indexX++) {  
            for (int indexY = y; indexY < y + 3; indexY++) {  
                if (board[indexX][indexY] == k) {  
                    return false;  
                }  
            }  
        }  
  
        return true;  
    }  
}