332. 重新安排行程
题目简述：
给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
思路
1. 利用字典储存所有路线
2. 每选择一条路线，就删除字典中的对应路线，看最后能否遍历完所有路线
3. 如果不能，就回溯；能就返回True
4. 字典序排序的实现使用sort函数实现，在选择路线的时候，优先选择排序后，靠前的路线
代码如下：
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
tree = {}
total = len(tickets) # 总共有多少条航线（几张机票）
# 生成一个字典 key是起飞机场，val是key可以到达的机场
for airline in tickets:
start = airline[0]
end = airline[1]
if start in tree:
tree[start].append(end)
else:
tree[start] = [end]
# 始发机场一定是JFK
ans = ['JFK']
# 开始 DFS
def dfs(total,start='JFK'):
# 如果剩余航线，即行程图没有边剩下，即可获得结果
if total == 0: # no ticket left
return True
# 如果还有行乘没有走完
# 且当前start是一个起飞机场，即有航线是从这里起飞
if start in tree:
# 字典序排序
tree[start].sort()
# 从起飞机场选择一个 落地机场降落
for _ in tree[start]:
# 处理落地机场
end = tree[start].pop(0)
ans.append(end)
total -= 1
# 如果飞到当前落地机场，能完成所有行乘
if dfs(total,end):
return True
# 如果飞到当前落地机场，不能完成所有行乘
# 回溯当前落地机场
else:
total += 1
ans.pop()
tree[start].append(end)
return False
dfs(total)
return ans
51. N皇后
题目简述
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
思路：
1. 设计一个函数专门判断当前位置是否可行，可以放皇后
2. 设计一个函数存储解法
3. 设计一个回溯函数不断row+1往深层走，再回溯
代码如下：
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
checkerboard=[0 for _ in range(n)]
res=[]
# 检查当前位置是否可行
def check(row,column):
# 遍历之前的行
for row_p in range(row):
# 检查是否在同一列
if checkerboard[row_p]==column:
return False
# 检查右上方是否有，行数+列数的值是否相等
if checkerboard[row_p]+row_p==row+column:
return False
# 检查左上方是否有,行数的差值与列数的差值是否相等
if row-row_p==column-checkerboard[row_p]:
return False
return True
def draw_q(k):
arr=[]
for i in range(k-1):
arr.append('.')
arr.append('Q')
for i in range(k,n):
arr.append('.')
return ''.join(i for i in arr)
def dfs(checkerboard,row,path):
if row==n:
res.append(path[:])
return
for col in range(n):
if check(row,col):
tmp=draw_q(col+1)
checkerboard[row]=col
path.append(tmp)
dfs(checkerboard,row+1,path)
path.pop()
checkerboard[row]=0
return
dfs(checkerboard,0,[])
return res
关键难点在判断当前位置是否可行上面
37. 解数独
题目简述：
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
思路：
1. 用line[i]，column[j]，block[x][y]分别表示第i行，第j列，第（x,y）给九宫格中填写数字的情况。
2. 九宫格的范围为0<=x<=2，以及0<=y<=2
3. 也即第i行，第j列的各自位于第（[i/3],[j/3]）个九宫格中，其中[]表示向下取整
代码如下
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def dfs(pos: int):
nonlocal valid
if pos == len(spaces):
valid = True
return
i, j = spaces[pos]
for digit in range(9):
if line[i][digit] == column[j][digit] == block[i // 3][j // 3][digit] == False:
line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True
board[i][j] = str(digit + 1)
dfs(pos + 1)
line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = False
if valid:
return
line = [[False] * 9 for _ in range(9)]
column = [[False] * 9 for _ in range(9)]
block = [[[False] * 9 for _a in range(3)] for _b in range(3)]
valid = False
spaces = list()
for i in range(9):
for j in range(9):
if board[i][j] == ".":
spaces.append((i, j))
else:
digit = int(board[i][j]) - 1
line[i][digit] = column[j][digit] = block[i // 3][j // 3][digit] = True
dfs(0)
标签：digit,return,37,51,day30,start,range,False,row From： https://www.cnblogs.com/cp1999/p/17317033.html