前言
代码随想录算法训练营day30
一、Leetcode 332.重新安排行程
1.题目
给你一份航线列表 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"]
示例 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. 1 <= tickets.length <= 300 2. tickets[i].length == 2 3. fromi.length == 3 4. toi.length == 3 5. fromi 和 toi 由大写英文字母组成 6. fromi != toi
来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/reconstruct-itinerary
2.解题思路
方法一：HierholzerHierholzer 算法
思路及算法
HierholzerHierholzer 算法用于在连通图中寻找欧拉路径，其流程如下：
1. 从起点出发，进行深度优先搜索。 2. 3. 每次沿着某条边从某个顶点移动到另外一个顶点的时候，都需要删除这条边。 4. 5. 如果没有可移动的路径，则将所在节点加入到栈中，并返回。
当我们顺序地考虑该问题时，我们也许很难解决该问题，因为我们无法判断当前节点的哪一个分支是「死胡同」分支。
不妨倒过来思考。我们注意到只有那个入度与出度差为 11 的节点会导致死胡同。而该节点必然是最后一个遍历到的节点。我们可以改变入栈的规则，当我们遍历完一个节点所连的所有节点后，我们才将该节点入栈(即逆序入栈)。
对于当前节点而言，从它的每一个非「死胡同」分支出发进行深度优先搜索，都将会搜回到当前节点。而从它的「死胡同」分支出发进行深度优先搜索将不会搜回到当前节点。也就是说当前节点的死胡同分支将会优先于其他非「死胡同」分支入栈。
这样就能保证我们可以「一笔画」地走完所有边，最终的栈中逆序地保存了「一笔画」的结果。我们只要将栈中的内容反转，即可得到答案。
3.代码实现
```java class Solution { Map > map = new HashMap >(); List itinerary = new LinkedList ();
1. public List<String> findItinerary(List<List<String>> tickets) { 2. for (List<String> ticket : tickets) { 3. String src = ticket.get(0), dst = ticket.get(1); 4. if (!map.containsKey(src)) { 5. map.put(src, new PriorityQueue<String>()); 6. } 7. map.get(src).offer(dst); 8. } 9. dfs("JFK"); 10. Collections.reverse(itinerary); 11. return itinerary; 12. } 13. 14. public void dfs(String curr) { 15. while (map.containsKey(curr) && map.get(curr).size() > 0) { 16. String tmp = map.get(curr).poll(); 17. dfs(tmp); 18. } 19. itinerary.add(curr); 20. }
}
```
二、Leetcode 51. N皇后
1.题目
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1 输出：[["Q"]]
提示：
1 <= n <= 9
来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/n-queens
2.解题思路
方法一：基于集合的回溯
为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合 columnscolumns、diagonals1diagonals1 和 diagonals2diagonals2 分别记录每一列以及两个方向的每条斜线上是否有皇后。
列的表示法很直观，一共有 NN 列，每一列的下标范围从 00 到 N−1N−1，使用列的下标即可明确表示每一列。
如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标之间的关系。
方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 (0,0)(0,0) 和 (3,3)(3,3) 在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。
fig1
方向二的斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，例如 (3,0)(3,0) 和 (1,2)(1,2) 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。
fig2
每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。
3.代码实现
```java class Solution { public List > solveNQueens(int n) { List > solutions = new ArrayList >(); int[] queens = new int[n]; Arrays.fill(queens, -1); Set columns = new HashSet (); Set diagonals1 = new HashSet (); Set diagonals2 = new HashSet (); backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2); return solutions; }
1. public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) { 2. if (row == n) { 3. List<String> board = generateBoard(queens, n); 4. solutions.add(board); 5. } else { 6. for (int i = 0; i < n; i++) { 7. if (columns.contains(i)) { 8. continue; 9. } 10. int diagonal1 = row - i; 11. if (diagonals1.contains(diagonal1)) { 12. continue; 13. } 14. int diagonal2 = row + i; 15. if (diagonals2.contains(diagonal2)) { 16. continue; 17. } 18. queens[row] = i; 19. columns.add(i); 20. diagonals1.add(diagonal1); 21. diagonals2.add(diagonal2); 22. backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2); 23. queens[row] = -1; 24. columns.remove(i); 25. diagonals1.remove(diagonal1); 26. diagonals2.remove(diagonal2); 27. } 28. } 29. } 30. 31. public List<String> generateBoard(int[] queens, int n) { 32. List<String> board = new ArrayList<String>(); 33. for (int i = 0; i < n; i++) { 34. char[] row = new char[n]; 35. Arrays.fill(row, '.'); 36. row[queens[i]] = 'Q'; 37. board.add(new String(row)); 38. } 39. return board; 40. }
}
```
三、Leetcode 37. 解数独
1.题目
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
1. 数字 1-9 在每一行只能出现一次。 2. 数字 1-9 在每一列只能出现一次。 3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 1：
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] 输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]] 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
提示：
1. board.length == 9 2. board[i].length == 9 3. board[i][j] 是一位数字或者 '.' 4. 题目数据 保证 输入数独仅有一个解
来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/sudoku-solver
2.解题思路
方法一：回溯
思路
最容易想到的方法是用一个数组记录每个数字是否出现。由于我们可以填写的数字范围为 [1,9][1,9]，而数组的下标从 00 开始，因此在存储时，我们使用一个长度为 99 的布尔类型的数组，其中 ii 个元素的值为 TrueTrue，当且仅当数字 i+1i+1 出现过。例如我们用 line[2][3]=Trueline[2][3]=True 表示数字 44 在第 22 行已经出现过，那么当我们在遍历到第 22 行的空白格时，就不能填入数字 44。
算法
我们首先对整个数独数组进行遍历，当我们遍历到第 ii 行第 jj 列的位置：
1. 如果该位置是一个空白格，那么我们将其加入一个用来存储空白格位置的列表中，方便后续的递归操作； 2. 3. 如果该位置是一个数字 xx，那么我们需要将 line[i][x−1]line[i][x−1]，column[j][x−1]column[j][x−1] 以及 block[⌊i/3⌋][⌊j/3⌋][x−1]block[⌊i/3⌋][⌊j/3⌋][x−1] 均置为 TrueTrue。
当我们结束了遍历过程之后，就可以开始递归枚举。当递归到第 ii 行第 jj 列的位置时，我们枚举填入的数字 xx。根据题目的要求，数字 xx 不能和当前行、列、九宫格中已经填入的数字相同，因此 line[i][x−1]line[i][x−1]，column[j][x−1]column[j][x−1] 以及 block[⌊i/3⌋][⌊j/3⌋][x−1]block[⌊i/3⌋][⌊j/3⌋][x−1] 必须均为 FalseFalse。
当我们填入了数字 xx 之后，我们要将上述的三个值都置为 TrueTrue，并且继续对下一个空白格位置进行递归。在回溯到当前递归层时，我们还要将上述的三个值重新置为 FalseFalse。
3.代码实现
```java class Solution { private boolean[][] line = new boolean[9][9]; private boolean[][] column = new boolean[9][9]; private boolean[][][] block = new boolean[3][3][9]; private boolean valid = false; private List
1. public void solveSudoku(char[][] board) { 2. for (int i = 0; i < 9; ++i) { 3. for (int j = 0; j < 9; ++j) { 4. if (board[i][j] == '.') { 5. spaces.add(new int[]{i, j}); 6. } else { 7. int digit = board[i][j] - '0' - 1; 8. line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true; 9. } 10. } 11. } 12. 13. dfs(board, 0); 14. } 15. 16. public void dfs(char[][] board, int pos) { 17. if (pos == spaces.size()) { 18. valid = true; 19. return; 20. } 21. 22. int[] space = spaces.get(pos); 23. int i = space[0], j = space[1]; 24. for (int digit = 0; digit < 9 && !valid; ++digit) { 25. if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) { 26. line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true; 27. board[i][j] = (char) (digit + '0' + 1); 28. dfs(board, pos + 1); 29. line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false; 30. } 31. } 32. }
}
```
![【蓝桥杯】[递归]母牛的故事](https://ucc.alicdn.com/pic/developer-ecology/2is4p5rpji74e_be870067c97c42ca9083c25b149faaa5.png?x-oss-process=image/resize,h_160,m_lfit)
