332.重新安排行程
方法一和方法二在力扣用例会超时
方法一、
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
tickets.sort()
res = []
used = [False]*len(tickets)
path = ['JFK']
self.tracebacking(tickets, used, path, res)
return res[0]
def tracebacking(self, tickets, used, path, res):
if len(path) == len(tickets) + 1: # 票用完了
res.append(path[:])
return True
# 获取当前所在机场和可以到达的目的地
cur_airport = path[-1]
for i, ticket in enumerate(tickets):
if used[i] == False and ticket[0] == cur_airport:
used[i] = True
path.append(ticket[1])
if self.tracebacking(tickets, used, path, res):
return
# 回溯
path.pop()
used[i] = False
return False # 没有找到有效路径
方法二
from collections import defaultdict
class Solution:
def findItinerary(self, tickets):
targets = defaultdict(list) # 创建默认字典,用于存储机场映射关系
for ticket in tickets:
targets[ticket[0]].append(ticket[1]) # 将机票输入到字典中
for key in targets:
targets[key].sort(reverse=True) # 对到达机场列表进行字母逆序排序
result = []
self.backtracking("JFK", targets, result) # 调用回溯函数开始搜索路径
return result[::-1] # 返回逆序的行程路径
def backtracking(self, airport, targets, result):
while targets[airport]: # 当机场还有可到达的机场时
next_airport = targets[airport].pop() # 弹出下一个机场
self.backtracking(next_airport, targets, result) # 递归调用回溯函数进行深度优先搜索
result.append(airport) # 将当前机场添加到行程路径中
方法三
from collections import defaultdict
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
# 机场到目的地的映射
targets = defaultdict(list)
for ticket in tickets:
targets[ticket[0]].append(ticket[1])
# 逆序排序下
for airport in targets:
targets[airport].sort(reverse=True)
res = []
self.dfs(targets, "JFK", res)
return res[::-1]
def dfs(self, targets, airport, res):
while targets[airport]:
dest = targets[airport].pop()
self.dfs(targets, dest, res)
res.append(airport)
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res = []
# 初始化棋盘
chessboard = ["." * n for _ in range(n)]
self.tracebacking(n, chessboard, 0, res)
return res
def tracebacking(self, n, chessboard, row, res):
if row == n:
res.append(chessboard[:])
return
for col in range(n):
if self.is_valid(chessboard, col, row):
chessboard[row] = chessboard[row][:col] + "Q" + chessboard[row][col+1:]
self.tracebacking(n, chessboard, row+1, res)
chessboard[row] = chessboard[row][:col] + "." + chessboard[row][col+1:]
def is_valid(self, chessboard, col, row):
# 判断列
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