代码随想训练营第三十天（Python）｜ 332.重新安排行程、51. N皇后-526互联

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)

51. N皇后

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