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

提示：

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

示例 1：

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

class Solution {
    LinkedList<String> res;
    LinkedList<String> path = new LinkedList<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
        path.add("JFK");
        boolean[] used = new boolean[tickets.size()];
        backTrack((ArrayList)tickets,used);
        return res;
    }
    private boolean backTrack(ArrayList<List<String>> tickets, boolean[] used) {
        if (path.size() == tickets.size() +  1) {
            res = new LinkedList(path);
            return true;
        }

        for (int i = 0;i < tickets.size(); i++) {
            if (!used[i] && tickets.get(i).get(0).equals(path.getLast())) {
                path.add(tickets.get(i).get(1));
                used[i] = true;

                if (backTrack(tickets, used)) {
                    return true;
                }

                used[i] = false;
                path.removeLast();
            }
        }
        return false;
    }
}

N皇后

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

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

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

class Solution {
    List<List<String>> res = new ArrayList<>();
    char[][] board;
    Set<Integer> cols = new HashSet<>();
    Set<Integer> diff = new HashSet<>();
    Set<Integer> sum = new HashSet<>();
    public List<List<String>> solveNQueens(int n) {
        if (n == 0) return res;
        board = new char[n][n];
        int i = 0, j = 0;
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        search(0, n);
        return res;
    }

    private void search(int idx, int n) {
        if (idx == n) {
            List<String> now = new ArrayList<>();
            for (int i = 0;i < n; i++) {
                now.add(String.valueOf(board[i]));
            }
            res.add(now);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!cols.contains(i) && !diff.contains(idx - i) && !sum.contains(idx + i)) {
                cols.add(i);
                diff.add(idx - i);
                sum.add(idx + i);
                board[idx][i] = 'Q';
                search(idx + 1, n);
                board[idx][i] = '.';
                diff.remove(idx - i);
                sum.remove(idx + i);
                cols.remove(i);
            }
        }
    }
}

37. 解数独

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

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

class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);
    }
    private boolean solve(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    continue;
                }
                for (int k = 1; k <= 9; k++) {
                    board[i][j] = (char)(k + '0');
                    if (isValid(board, i, j) && solve(board)) {
                        return true;
                    }
                    board[i][j] = '.';
                }
                return false;
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int a, int b) {
        Set<Character> contained = new HashSet<>();
        for (int j = 0; j < 9; j++) {
            if (contained.contains(board[a][j])) return false;
            if (board[a][j] > '0' && board[a][j] < '9') {
                contained.add(board[a][j]);
            }
        }
        contained = new HashSet<>();
        for (int j = 0; j < 9; j++) {
            if (contained.contains(board[j][b])) return false;
            if (board[j][b] > '0' && board[j][b] <= '9') {
                contained.add(board[j][b]);
            }
        }

        contained = new HashSet<Character>();
        for (int m = 0; m < 3; m++) {
            for (int n = 0; n < 3; n++) {
                int x = a / 3 * 3 + m, y = b / 3 * 3 + n;
                if (contained.contains(board[x][y])) {
                    return false;
                }
                if (board[x][y] > '0' && board[x][y] <= '9') {
                    contained.add(board[x][y]);
                }
            }
        }
        return true;
    }
}

526互联

代码随想录day 30 332.重新安排行程 | n皇后 | 37. 解数独

37. 解数独