【代码随想录训练营】【Day 32】【回溯-6】【待二刷】| Leetcode 332, 51, 37

• sort reverse的用法，以及result.append(airport)的理解

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)  # 将当前机场添加到行程路径中

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:result = []chessboard = ['.' * n for _ in range(n)]self.backtracking(result, chessboard, n, 0)return resultdef backtracking(self, result, chessboard, n, row):if row == n:result.append(chessboard[:])returnfor col in range(n):if self.isVaild(chessboard, row, col):chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col+1:]self.backtracking(result, chessboard, n, row+1)chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col+1:]def isVaild(self, chessboard, row, col):for i in range(row):if chessboard[i][col] == 'Q':return Falsei, j = row-1, col-1while i >= 0 and j>= 0:if chessboard[i][j] == 'Q':return Falsei -= 1j -= 1i, j = row-1, col+1while i >=0 and j < len(chessboard):if chessboard[i][j] == 'Q':return Falsei -= 1j += 1return True

class Solution:def solveSudoku(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""self.backtracking(board)def backtracking(self, board: List[List[str]]) -> bool:# 若有解，返回True；若无解，返回Falsefor i in range(len(board)): # 遍历行for j in range(len(board[0])):  # 遍历列# 若空格内已有数字，跳过if board[i][j] != '.': continuefor k in range(1, 10):if self.is_valid(i, j, k, board):board[i][j] = str(k)if self.backtracking(board): return Trueboard[i][j] = '.'# 若数字1-9都不能成功填入空格，返回False无解return Falsereturn True # 有解def is_valid(self, row: int, col: int, val: int, board: List[List[str]]) -> bool:# 判断同一行是否冲突for i in range(9):if board[row][i] == str(val):return False# 判断同一列是否冲突for j in range(9):if board[j][col] == str(val):return False# 判断同一九宫格是否有冲突start_row = (row // 3) * 3start_col = (col // 3) * 3for i in range(start_row, start_row + 3):for j in range(start_col, start_col + 3):if board[i][j] == str(val):return Falsereturn True