题目简介
注意今天的题目都是困难题，理解较为困难，可以先跳过。
332. 重新安排行程
给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
51. N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
37. 解数独
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
初见思路
- 想普通的解法，可以过两个测试用例，但是实际提交的时候却超时。有两个要点，对于tickets数量为N，那么合法的路径长度是N+1，这个是终止条件；遍历每一个机票组合，要使用数组记录访问的情况，对于已访问的组合不再重复访问。（遍历前先按字典序排序机票组合，那么排序完之后所有遍历结果的第一个则是需求解。）
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
tickets.sort() # 按照字典序自动排序
self.visited = [False] * len(tickets)
self.path = ['JFK']
self.result = list()
self.back_tracking(tickets, 'JFK')
return self.result[0]
def back_tracking(self,tickets,cur) -> bool:
if len(self.path) == len(tickets)+1:
self.result.append(self.path[:])
return True
for i,ticket in enumerate(tickets):
if ticket[0] == cur and not self.visited[i]:
self.visited[i] = True
self.path.append(ticket[1])
is_valid_ans = self.back_tracking(tickets, ticket[1])
self.path.pop()
self.visited[i] = False
if is_valid_ans:
return True
- 三个要点：1，怎么判断皇后的位置合不合法 2，皇后每次怎么摆放？=》取决于上一行的皇后怎么摆 3，终止条件是什么？=〉一行行摆放皇后能摆放到第N行
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
result = []
chessboard = ['.' * n for _ in range(n)]
self.backtracking(n, 0, chessboard, result)
return [[''.join(row) for row in solution] for solution in result]
def backtracking(self, n: int, row: int, chessboard: List[str], result: List[List[str]]) -> None:
if row == n:
result.append(chessboard[:])
return
for col in range(n):
if self.isValid(row, col, chessboard):
chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col+1:]
self.backtracking(n, row + 1, chessboard, result) # 递归到下一行
chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col+1:]
def isValid(self, row: int, col: int, chessboard: List[str]) -> bool:
# 检查列
for i in range(row):
if chessboard[i][col] == 'Q':
return False
# 检查 45 度角是否有皇后
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if chessboard[i][j] == 'Q':
return False
i -= 1
j -= 1
# 检查 135 度角是否有皇后
i, j = row - 1, col + 1
while i >= 0 and j < len(chessboard):
if chessboard[i][j] == 'Q':
return False
i -= 1
j += 1
return True # 当前位置合法
- 解数独。（时间不够今天先跳过）
复盘思路
- 看到的lc上最牛的解法, 首先对机票构建图，然后对每个出发点能到达的目的地逆序排序
import collections
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
graph = collections.defaultdict(list)
for start, end in tickets:
graph[start].append(end)
for city in graph:
graph[city].sort(reverse=True)
path = collections.deque()
def backtracking(cur_city):
while graph[cur_city]:
next_city = graph[cur_city].pop()
backtracking(next_city)
path.appendleft(cur_city)
backtracking('JFK')
return list(path)
重点难点
https://programmercarl.com/0332.%E9%87%8D%E6%96%B0%E5%AE%89%E6%8E%92%E8%A1%8C%E7%A8%8B.html
https://programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html
https://programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html
