代码随想录算法训练营Day30 | 332.重新安排行程、51. N皇后、37. 解数独、回溯算法总结 | Python | 个人记录向

本文主要是介绍代码随想录算法训练营Day30 | 332.重新安排行程、51. N皇后、37. 解数独、回溯算法总结 | Python | 个人记录向，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

332.重新安排行程

代码随想录：332.重新安排行程
Leetcode：332.重新安排行程

做题

无思路。

看文章

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

感觉比较有意思的是，这样处理一定能找出唯一的路径。先碰到后续为None的机场，才存入result数组，然后再逆序输出结果。
文章其实主要提到了容器的选择，这里用python，基本就是dict或者defaultdict。

51. N皇后

代码随想录：51. N皇后
Leetcode：51. N皇后

做题

无思路。感觉回溯其实就是遍历？但在遍历中如何移动皇后？随机移动吗？

看文章

核心为写isValid函数，判断是否能在当前位置放置皇后。这里注意的是：初始化chessboard时，每一行都是一个字符串，整个chessboard是一个list，故在放置或拿开皇后时，只能用字符串拼接，而不能直接修改str。如果将chessboard设置成二维list，在在放置或拿开皇后时，可以直接修改每一行元素，但需要对二维数组进行深拷贝。

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[:])  # 棋盘填满，将当前解加入结果集returnfor 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 - 1while i >= 0 and j >= 0:if chessboard[i][j] == 'Q':return False  # 左上方向已经存在皇后，不合法i -= 1j -= 1# 检查 135 度角是否有皇后i, j = row - 1, col + 1while i >= 0 and j < len(chessboard):if chessboard[i][j] == 'Q':return False  # 右上方向已经存在皇后，不合法i -= 1j += 1return True  # 当前位置合法

时间复杂度: O(n!)
空间复杂度: O(n)

将chessboard设置成二维list的AC代码：

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(copy.deepcopy(chessboard))  # 棋盘填满，将当前解加入结果集returnfor col in range(n):if self.isValid(row, col, chessboard):chessboard[row][col] = 'Q' # 放置皇后self.backtracking(n, row + 1, chessboard, result)  # 递归到下一行chessboard[row][col] = '.'  # 回溯，撤销当前位置的皇后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 - 1while i >= 0 and j >= 0:if chessboard[i][j] == 'Q':return False  # 左上方向已经存在皇后，不合法i -= 1j -= 1# 检查 135 度角是否有皇后i, j = row - 1, col + 1while i >= 0 and j < len(chessboard):if chessboard[i][j] == 'Q':return False  # 右上方向已经存在皇后，不合法i -= 1j += 1return True  # 当前位置合法

这种写法在复杂度上差不多，但个人比较喜欢，主要是因为在修改字符时比较好理解，但二维数组需要进行深拷贝，具体为result.append(copy.deepcopy(chessboard))。

37. 解数独

代码随想录：37. 解数独
Leetcode：37. 解数独

做题

isValid函数可以写出来，回溯部分卡壳了。

看文章

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

这里有个点，递归是从头重新遍历，是不是可以从下一个位置遍历？不行！因为代码是一个一个数字放的，而不是一个一个格子遍历。

回溯算法总结

代码随想录：回溯算法总结
熟悉常见提醒后，可以再看看复杂度的计算。

以往忽略的知识点小结

• 灵活使用defaultdict
• 棋盘问题，主要是写isValid函数，然后回溯（N皇后：放和不放；数独：放哪个数字）
• 二维数组需要进行深拷贝，比如copy.deepcopy(chessboard)

个人体会

完成时间：1h50min。
心得：题比较难，时间比较紧张，主要是熟悉思路。

​

这篇关于代码随想录算法训练营Day30 | 332.重新安排行程、51. N皇后、37. 解数独、回溯算法总结 | Python | 个人记录向的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---