一个外国人做的汉子 网站,现有电商平台,国外公共空间设计网站,wordpress模板仿qq空间目录
详细布置#xff1a;
1. 回溯总结
2. 332. 重新安排行程
3. 51. N 皇后
4. 37. 解数独 详细布置#xff1a;
1. 回溯总结
回溯是递归的副产品#xff0c;只要有递归就会有回溯#xff0c;所以回溯法也经常和二叉树遍历#xff0c;深度优先搜索混在一起#x…目录
详细布置
1. 回溯总结
2. 332. 重新安排行程
3. 51. N 皇后
4. 37. 解数独 详细布置
1. 回溯总结
回溯是递归的副产品只要有递归就会有回溯所以回溯法也经常和二叉树遍历深度优先搜索混在一起因为这两种方式都是用了递归。
回溯法就是暴力搜索并不是什么高效的算法最多再剪枝一下。
回溯算法能解决如下问题
组合问题N个数里面按一定规则找出k个数的集合排列问题N个数按一定规则全排列有几种排列方式切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集棋盘问题N皇后解数独等等
详细总结可以移步代码随想录回溯总结- 代码随想录 2. 332. 重新安排行程 给你一份航线列表 tickets 其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 所有这些机票都属于一个从 JFK肯尼迪国际机场出发的先生所以该行程必须从 JFK 开始。如果存在多种有效的行程请你按字典排序返回最小的行程组合。 例如行程 [JFK, LGA] 与 [JFK, LGB] 相比就更小排序更靠前。 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。 直觉上来看 这道题和回溯法没有什么关系更像是图论中的深度优先搜索。
实际上确实是深搜但这是深搜中使用了回溯的例子在查找路径的时候如果不回溯怎么能查到目标路径呢。
所以我倾向于说本题应该使用回溯法那么我也用回溯法的思路来讲解本题其实深搜一般都使用了回溯法的思路在图论系列中我会再详细讲解深搜。
这里就是先给大家拓展一下原来回溯法还可以这么玩
这道题目有几个难点
一个行程中如果航班处理不好容易变成一个圈成为死循环有多种解法字母序靠前排在前面让很多同学望而退步如何该记录映射关系呢 使用回溯法也可以说深搜 的话那么终止条件是什么呢搜索的过程中如何遍历一个机场所对应的所有机场。
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(reverseTrue) # 对到达机场列表进行字母逆序排序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) # 将当前机场添加到行程路径中 3. 51. N 皇后 按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。 给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位。 4. 37. 解数独 编写一个程序通过填充空格来解决数独问题。 数独的解法需 遵循如下规则 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图 数独部分空格内已填入了数字空白格用 . 表示。 N皇后问题 是因为每一行每一列只放一个皇后只需要一层for循环遍历一行递归来遍历列然后一行一列确定皇后的唯一位置。
本题就不一样了本题中棋盘的每一个位置都要放一个数字而N皇后是一行只放一个皇后并检查数字是否合法解数独的树形结构要比N皇后更宽更深。 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
