332.重新安排行程

题目链接

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

51.N皇后

题目链接

讲解链接

n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。意思就是每个皇后不能处于同行、同列或同斜线上。本题的树形结构如下：

树的每一层递归对应棋盘的一行，深度对应n，宽度为n*n。

回溯三部曲：

1.递归函数参数及返回值：参数为表示棋盘的字符串列表chessboard和遍历到的行数row以及n。

def backtracking(self, chessboard, row, n):

2.递归终止条件：当row == n时，说明已经递归到了棋盘的最后一行，此时应该收集结果并返回。

if row == n:
    self.result.append(chessboard[:])
    return

3.单层递归逻辑：通过row来遍历棋盘的行，col遍历棋盘的列。每次都是从当前行的第1列开始遍历，所以col在每一轮循环中都是从0开始的。再通过isvalid函数判断当前位置放置皇后是否合法。

for col in range(0, n):
    if self.isvalid(chessboard, row, col):
        chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col + 1:]
        self.backtracking(chessboard, row + 1, n)
        chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col + 1:]

整体代码如下：

class Solution:
    def __init__(self):
        self.result = []  # 储存结果
    def isvalid(self, chessboard, row, col):
        for i in range(row):  # 判断同列是否存在皇后
            if chessboard[i][col] == 'Q':
                return False
        i, j = row - 1, col - 1  # 判断左上角方向是否存在皇后
        while i >= 0 and j >= 0:
            if chessboard[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        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
    def backtracking(self, chessboard, row, n):
        if row == n:  # 终止条件
            self.result.append(chessboard[:])  # 收集结果
            return
        for col in range(0, n):  # 每一行都从第0列开始遍历
            if self.isvalid(chessboard, row, col):  # 判断是否合法
                chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col + 1:]  # 由于不能直接进行赋值，需要通过切片的方式来将row行col列位置的元素赋值为‘Q’
                self.backtracking(chessboard, row + 1, n)
                chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col + 1:]  # 回溯过程，将该位置变回‘.’
    def solveNQueens(self, n: int) -> List[List[str]]:
        chessboard = ['.' * n for _ in range(n)]  # 初始化棋盘
        self.backtracking(chessboard, 0, n)
        return self.result

37.解数独

题目链接

讲解链接

N皇后是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来遍历列，然后一行一列确定皇后的唯一位置。本题就不一样了，本题中棋盘的每一个位置都要放一个数字（而N皇后是一行只放一个皇后），并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。

回溯三部曲：

1.递归函数参数及返回值：递归函数的返回值需要是bool类型，因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用bool返回值。

def backtracking(self, board):

2.递归终止条件：解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止（填满说明找到了结果），所以不需要终止条件。

3.单层搜索逻辑：在树形图中可以看出我们需要的是一个二维的递归 （一行一列）一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！

for row in range(len(board)):
    for col in range(len(board[0])):
        if board[row][col] != '.': 
            continue
        for k in range(1, 10):
            if self.isvalid(row, col, k, board):
            board[row][col] = str(k)
            if self.backtracking(board):
                return True
            board[row][col] = '.'
        return False
return True

整体代码如下：

class Solution:
    def isvalid(self, row, col, k, board):  # 判断当前格内数字是否合法
        for i in range(9):  # 查找同行中是否存在相同数字
            if board[row][i] == str(k):
                return False
        for i in range(9):  # 查找同列中是否存在相同数字
            if board[i][col] == str(k):
                return False
        row_k = (row // 3) * 3  # 当前位置所处九宫格的起始行
        col_k = (col // 3) * 3  # 当前位置所处九宫格的起始列
        for i in range(row_k, row_k + 3):  # 判断九宫格中是否存在相同数字
            for j in range(col_k, col_k + 3):
                if board[i][j] == str(k):
                    return False
        return True
    def backtracking(self, board):  # 返回值为bool类型，若找到合法结果就直接返回True
        for row in range(len(board)):  # 第一个for循环遍历行
            for col in range(len(board[0])):  # 第二个for循环遍历列
                if board[row][col] != '.':   # 如果当前位置不为空则直接跳过
                    continue
                for k in range(1, 10):  # 从1到10依次填入数字
                    if self.isvalid(row, col, k, board):  # 判断当前填入的k值是否合法
                        board[row][col] = str(k)  # 将k转为字符形式填入
                        if self.backtracking(board):  # 递归向下一个空格内填入数字
                            return True  # 若返回均为True则说明找到了一组结果
                        board[row][col] = '.'  # 回溯，将之前填上的不符合条件的数字恢复为‘.’
                return False  # 若填入1到10都不符合则说明无解
        return True  # 遍历结束则说明填满了棋盘，找到了一组解
    def solveSudoku(self, board: List[List[str]]) -> None:
        self.backtracking(board)