今日任务：
1）332.重新安排行程
2）51.N皇后
3）37.解数独
332.重新安排行程
题目链接：332. 重新安排行程 - 力扣（LeetCode）
给定一个机票的字符串二维数组 [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"]。但是它自然排序更大更靠后
文章讲解：代码随想录 (programmercarl.com)
思路：
这道题目是典型的图的遍历问题，可以使用深度优先搜索（DFS）来解决。思路如下：
- 首先，将机票信息存储在一个字典中，键为起始机场，值为从该机场出发的所有目的地的列表。
- 对每个起始机场的目的地列表进行排序，以保证在遍历时按字典序选择下一个机场。
- 从起始机场 JFK 开始，进行深度优先搜索，每次选择下一个目的地时，将该目的地从目的地列表中删除，表示已经使用过。
- 搜索过程中，如果某个机场的目的地列表为空，则说明到达了终点，返回当前路径。
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
# 构建邻接表，键为起始机场，值为从该机场出发的目的地列表
graph = defaultdict(list) # 使用 defaultdict(list) 来创建一个默认值为列表的字典。这样，如果访问字典中不存在的键时，将返回一个空列表作为默认值。
for start, end in tickets:
# print(f'start:{start},end:{end}') # start:JFK,end:SFO
graph[start].append(end)
# print(graph)
# 对目的地列表进行排序，保证按字典序选择下一个机场
for start in graph:
graph[start].sort()
# print(graph)
# 存储结果的列表
self.result = []
self.dfs('JFK',graph)
return self.result
# 定义深度优先搜索函数
def dfs(self,start,graph):
while graph[start]:
# 选择当前机场的下一个目的地
next_dest = graph[start].pop(0)
self.dfs(next_dest,graph)
# 在结果列表的最前面插入当前机场，表示当前路径
self.result.insert(0, start)感想：
这题要注意的是递归到叶子节点，所以先收集的是叶子节点，然后往回收集，所以我们这里应该是在结果的最前面插入当前机场
51.N皇后
题目链接：51. N 皇后 - 力扣（LeetCode）
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
文章讲解：代码随想录 (programmercarl.com)
视频讲解：这就是传说中的N皇后？ 回溯算法安排！| LeetCode：51.N皇后哔哩哔哩bilibili
思路：
- 定义一个二维数组来表示棋盘，初始化为全部为 '.'，表示空位。
- 从第一行开始，逐行放置皇后。
- 在每一行中，尝试将皇后放置在该行的每一个位置，检查是否与已放置的皇后冲突。
- 冲突条件：新放置的皇后与已放置的皇后在同一列、同一行或同一条对角线上。
- 如果找到一个位置可以放置皇后，则递归进入下一行，继续放置下一个皇后。
- 如果无法找到一个位置放置皇后，则回溯到上一行，尝试放置下一个位置的皇后。
- 当成功放置了 n 个皇后时，将当前棋盘状态加入结果列表中。
- 继续回溯，直到遍历完所有可能的情况
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
self.n = n
self.result = []
# 初始化棋盘
# self.board = [['.'] * n] * n # 虽然看起来是创建了一个 n × n 大小的二维列表，但实际上每一行都是相同的列表对象的引用。这意味着如果你修改了一个行的内容，其他行也会受到影响，因为它们共享相同的子列表。
self.board = [['.' for _ in range(n)] for _ in range(n)]
# print(f'初始化board-->{self.board}')
self.backtracking(0)
return self.result
def is_valid(self, row, col):
# print(f'点{(row,col)}')
# 检查列上是否有皇后
for i in range(row):
if self.board[i][col] == 'Q':
return False
# 检查左上方是否有皇后
for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
# print(f'左上：{(i,j)}')
if self.board[i][j] == 'Q':
return False
# 检查右上方是否有皇后
for i, j in zip(range(row - 1, -1, -1), range(col + 1, self.n)):
# print(f'右上：{(i,j)}')
if self.board[i][j] == 'Q':
return False
return True
def backtracking(self, row):
# 如果当前行超过了棋盘大小，说明找到了一个解
if row == self.n:
self.result.append(["".join(row) for row in self.board])
return
# 在当前行的每个位置尝试放置皇后
for col in range(self.n):
if self.is_valid(row, col):
self.board[row][col] = 'Q'
self.backtracking(row + 1)
self.board[row][col] = '.' # 回溯感想：
在这里面之前犯了一个错误self.board = [['.'] * n] * n
虽然看起来是创建了一个 n × n 大小的二维列表，但实际上每一行都是相同的列表对象的引用。这意味着如果你修改了一个行的内容，其他行也会受到影响，因为它们共享相同的子列表。
为了避免这种情况，可以使用列表解析或循环来创建独立的子列表
self.board = [['.' for _ in range(n)] for _ in range(n)]
37.解数独
题目链接：37. 解数独 - 力扣（LeetCode）
编写一个程序，通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。
文章讲解：代码随想录 (programmercarl.com)
视频讲解：回溯算法二维递归？解数独不过如此！| LeetCode：37. 解数独哔哩哔哩bilibili
思路：
- 使用回溯法解决数独问题。
- 递归地尝试在每个空白格子中填入数字，然后检查是否满足数独规则。
- 如果满足规则，则继续向下递归填写下一个空白格子，直到填满整个数独棋盘。
- 如果某个格子无法填入任何数字，则回溯到上一个格子重新尝试。
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if self.backtracking(board):
print(board)
def backtracking(self,board):
# 遍历整个数独棋盘
for i in range (9):
for j in range(9):
# 如果当前格子不为空白，跳过
if board[i][j] != '.':
continue
# 尝试填入数字1-9
for num in map(str, range(1, 10)):
# 如果填入的数字符合数独规则
if self.is_valid(board,i,j,num):
board[i][j] = num
# 递归调用 solve 函数，继续填下一个空白格子
if self.backtracking(board):
return True
# 如果填入的数字导致无解，则回溯到上一个格子，重新尝试其他数字
board[i][j] = '.'
# 遍历完1-9，还没有被返回，说明当前格子无法填入任何数字，则返回 False
return False
# 遍历完所有格子，还没有被False提前返回，说明所有空白格子都填满了，则表示找到了解法，返回 True
return True
def is_valid(self,board,row,col,num):
"""
检查填入的数字是否符合数独规则
"""
# 检查行和列是否有重复数字
for i in range(9):
if board[row][i] == num or board[i][col] == num:
return False
# 检查3x3宫内是否有重复数字
for i in range(3):
for j in range(3):
if board[(row//3)*3 + i][(col//3)*3 + j] == num:
return False
return True感想：
这题与N皇后不一样的是有三个维度，不仅要遍历行列，确定一个位置后，还要依次填入1-9的数字
