代码随想录D24-25 回溯算法03-04 Python

目次
93. 复原 IP 地点
78. 子集 子集题目
90. 子集 II
491. 非递减子序列
46. 全分列 分列题目
47. 全分列 II
332. 重新安排行程 利用字典实现图
51. N 皇后 多维题目入门
37. 解数独 

---

 
93. 复原 IP 地点

要点：

本质上和上一期的回文字串切分是相似的，题意已经明白，每个字段都需要满足0到255的要求，因此，将要求作为一次递归的终止条件即可。
解法：

输入输出：
1. 原始数组；
2. startindex：用于指示当前的切割位置，避免重复分割
3. path：IP地点每个字段构成的路径
4. results：总结果
终止条件：
起首判断当前path中是否已经有三个元素，假如末了一个字段也符合要求，那么就可以终止并返回结果了
单步逻辑：
从startindex开始切分若干个结果，结果的要求需要符合题意，不能以0开始，且数值不能大于255。这是递归的单层逻辑。
实现：

1. class Solution:
3.     ## 根据规则预定义一个判断函数 判断每段截取的字段是否合规
4.     def is_valid(self, s, start, end):
5.         if start > end:
6.             return False
7.         # 0开头且长度大于1的数字不合法
8.         if s[start] == '0' and start != end:  
9.             return False
10.         num = int(s[start:end+1])
12.         return 0 <= num <= 255
14.     def backtrack(self, s, start_idx, path, results):
15.         ## 判断数组长度和start_idx指向的位置决定是否返回
16.         if len(path) == 4 and start_idx == len(s):
17.             results.append('.'.join(path))
18.             return
20.         elif len(path) > 4:
21.             return
23.         ## 指定i的边界 防止最后一位索引出界
24.         for i in range(start_idx, min(start_idx + 3, len(s))):
25.             
26.             if self.is_valid(s, start_idx, i):
27.                 part_str = s[start_idx: i + 1]
28.                 path.append(part_str)
29.                 self.backtrack(s, i + 1, path, results)
30.                 path.pop()
31.             
33.     def restoreIpAddresses(self, s: str) -> List[str]:
34.         
35.         results = list()
36.         self.backtrack(s, 0, [], results)
37.         
38.         return results

复制代码

78. 子集

 要点 子集题目：

假如把 子集题目、组合题目、分割题目都抽象为一棵树的话，那么组合题目和分割题目都是收集树的叶子节点，而子集题目是找树的所有节点！
其实子集也是一种组合题目，因为它的聚集是无序的。由于无序，所以写算法时依然需要一个start_index来控制取样不重复。
相对地，求分列题目的时间，就要从0开始，因为聚集是有序的，{1, 2} 和 {2, 1}是两个聚集。
求所有节点的运算逻辑如下： 

 解法：

输入输出：
1. 输入数组；2. 起始索引；3. 路径；4. 所有结果
终止条件：
可以不设置终止条件
单步逻辑：
求取子集题目，不需要任何剪枝。因为子集就是要遍历整棵树。在每一个递归逻辑中搜集聚集。
 实现：

1. class Solution:
3.     def backtrack(self, nums, start_idx, path, result):
4.         
5.         ## 每个递归之前将当前path的子集结果输入
6.         result.append(path[:])
8.         for i in range(start_idx, len(nums)):
9.             path.append(nums[i])
10.             ## 根据i确定后续横向遍历起始位置
11.             self.backtrack(nums, i + 1, path, result)
12.             path.pop()
14.     def subsets(self, nums: List[int]) -> List[List[int]]:
15.         
16.         result = list()
17.         self.backtrack(nums, 0, [], result)
19.         return result

复制代码

90. 子集 II

要点：

回溯算法中的去重题目，在40.组合总和II (opens new window)中已经详细解说过了，和本题是一个套路。后面的分列题目里去重也是这个套路，所以明白“树层去重”和“树枝去重”非常紧张。

回顾一下去重思路，起首需要对数组进行一个排序，利用used数组作为一个标记来记录前一个元素是否已经经过了遍历。随后，在横向遍历过程中，假如当前索引下的used的上一位是0，且当前元素和上一位的元素相同，这就说明这里是在重复进行上一个元素的遍历，跳过即可。
解法：

和组合去重非常相似，紧张的是注意提前排序，否则会出现重复。
结果记录逻辑遵照幂集返回全部的规则，因此无需添加额外终止条件。
实现：

1. class Solution:
3.     def backtrack(self, nums, used, start_idx, path, results):
5.         results.append(path[:])
7.         for i in range(start_idx, len(nums)):
8.             if i > 0 and nums[i] == nums[i - 1] and used[i - 1] == 0:
9.                 continue
11.             path.append(nums[i])
12.             used[i] = 1
13.             self.backtrack(nums, used, i + 1, path, results)
14.             used[i] = 0
15.             path.pop()
16.             
19.     def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
20.         
21.         nums = sorted(nums)
22.         path, results = list(), list()
23.         used = [0] * len(nums)
25.         self.backtrack(nums, used, 0, path, results)
27.         return results

复制代码

491. 非递减子序列

要点：

这个递增子序列比力像是取有序的子集。而且本题也要求不能有相同的递增子序列。这里要求去重，但是由于题目本身的限制，我们不能对输入数组进行排序。因此要换一种去重逻辑

 可以看到这里利用了一个树层去重的方案，在同一树层中，假如当前取的元素已经有数值相同的元素被取过了，那么就要去重了。
解法：

输入输出：1.输入数组；2.起始索引；3.当前路径；4.终极结果
终止条件：当索引位置到达末了一个元素时终止步伐
单步逻辑：for循环遍历起始索引到len(nums)的元素，利用一个聚集判断在每一个树层中没有重复利用的元素
实现：

1. class Solution:
3.     def backtrack(self, nums, start_idx, path, results):
4.         if len(path) > 1:
5.             results.append(path[:])
7.         used = set()
8.         for i in range(start_idx, len(nums)):
9.             if (nums[i] in used) or (len(path) > 0 and nums[i] < path[-1]):
10.                 continue
11.             
12.             used.add(nums[i])
13.             path.append(nums[i])
14.             self.backtrack(nums, i + 1, path, results)
15.             path.pop()
18.     def findSubsequences(self, nums: List[int]) -> List[List[int]]:
19.         
20.         path, results = list(), list()
21.         self.backtrack(nums, 0, path, results)
23.         return results

复制代码

46. 全分列

 要点：

分列题目不需要利用startIndex了，因为取元素时会遇到无序的情况。但分列题目需要一个used数组，标记已经选择的元素，如许才可以包管取元素时的正确性。

解法：

输入输出：1.输入数组；2.used数组记录元素利用情况；3.当前路径path；4.终极结果results
单步逻辑：利用used判断当前索引是否已经被利用，被利用则跳过
终止条件：收集元素的数组path的巨细到达和nums数组一样大的时间，说明找到了一个全分列，也表示到达了叶子节点。
实现：

1. class Solution:
3.     def backtrack(self, nums, used, path, results):
5.         if len(path) == len(nums):
6.             results.append(path[:])
7.         
8.         for i in range(len(nums)):
9.             if used[i]:
10.                 continue
11.             
12.             used[i] = True
13.             path.append(nums[i])
14.             self.backtrack(nums, used, path, results)
15.             path.pop()
16.             used[i] = False
19.     def permute(self, nums: List[int]) -> List[List[int]]:
20.         
21.         used = [False] * len(nums)
22.         path, results = list(), list()
23.         self.backtrack(nums, used, path, results)
25.         return results

复制代码

47. 全分列 II

要点：

这道题目和46.全分列 (opens new window)的区别在与给定一个可包含重复数字的序列，要返回所有不重复的全分列。这里又涉及到去重了。数组的去重肯定要对元素进行排序，如许我们才方便通过相邻的节点来判断是否重复利用了。

一般来说：组合题目和分列题目是在树形布局的叶子节点上收集结果，而子集题目就是取树上所有节点的结果。
解法：

输入输出：参加一个used来对树层上的重复利用进行判断
终止条件：path的长度等于输入数组的长度时终止
单步逻辑：普通分列检查当前数值是否已经被利用，这里要转换成同树层前一位是否被读取了
实现：

1. class Solution:
3.     def backtrack(self, nums, used, path, results):
5.         if len(path) == len(nums):
6.             results.append(path[:])
7.         
9.         for i in range(len(nums)):
10.             ## 通过两个条件过滤掉两种可能的重复
11.             if (i > 0 and used[i - 1] == 0 and nums[i] == nums[i - 1]) or used[i] == 1:
12.                 continue
13.             
14.             path.append(nums[i])
15.             used[i] = 1
16.             self.backtrack(nums, used, path, results)
17.             used[i] = 0
18.             path.pop()
21.     def permuteUnique(self, nums: List[int]) -> List[List[int]]:
22.         
23.         nums = sorted(nums)
24.         used = [0] * len(nums)
25.         path, results = list(), list()
27.         self.backtrack(nums, used, path, results)
29.         return results

复制代码

332. 重新安排行程

• JFK - 约翰·F·肯尼迪国际机场 (John F. Kennedy International Airport)，位于美国纽约。
  
• MUC - 慕尼黑机场 (Munich Airport)，位于德国慕尼黑。
  
• LHR - 伦敦希思罗机场 (London Heathrow Airport)，位于英国伦敦。
  
• SFO - 旧金山国际机场 (San Francisco International Airport)，位于美国旧金山。
  
• SJC - 圣荷西国际机场 (San Jose International Airport)，位于美国加利福尼亚州圣荷西。
  

要点：

本题是回溯法的一个拓展，这道题目有几个难点：

• 一个行程中，假如航班处理不好轻易变成一个圈，成为死循环
  
• 有多种解法，字母序靠前排在前面，怎样该记录映射关系呢 ？
  
• 利用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？
  
• 搜刮的过程中，怎样遍历一个机场所对应的所有机场。
  

1. 死循环：由案例2可以看到，部分情况下会持有往返机票，假如往返的行程字典序靠前，且没有处理好去重，那么就会陷入死循环。明白为一张机票只能用一次。
2. 映射关系：单个出发地会映射多个可及的目的地，这里需要利用字典进行处理
3. 回溯树形布局：

解法：

0. 外层准备：
将机票信息转换为图的连接表，提前做好反序方便弹出调用，包管每张票只用一次
1. 输入输出：
假设想要找到符合排序的路径，可以以当前所在的机场作为输入，然后遍历当前出发点的所有可达目的地，按照排序来挑选符合要求的目的地。因此，回溯的输入包括：1.当前位置；2.机票信息（处理成字典方便按出发地查找）；3.终极结果。也可以记录一个path，不外既然只要取最优结果，就可以在回溯过程做好分列，确保每次参加的行程是最优的即可
2. 终止条件：
假如当前机场已经没有能去的目的地，就要终止了；由于测试例可以或许包管肯定有解，因此可以不参加行程的长度判断，这表示
3. 单步逻辑：
利用pop弹出优先的目的地，题意包管了这条路线是可以探索到底的；
将目的地作为新的出发点继续遍历，出递归后输出结果。
实现：

1. class Solution:
3.     def backtrack(self, ticket_dict, department, results):
5.         while ticket_dict[department]:
6.             ## 这里用字典的键中pop 因此需要提前做好反序
7.             ## 这个行为可以保证每次先推出排序靠前的目的地 且每张机票只能用一次
8.             ## 如果后续目的地都是合法的 那么就可以持续递归到最终结果
9.             terminal = ticket_dict[department].pop()
10.             self.backtrack(ticket_dict, terminal, results)
11.         ## 这里将出发点记录在路径中 出回溯之后才会添加出发地
12.         ## 因此添加顺序是反向的
13.         results.appendleft(department)
16.     def findItinerary(self, tickets: List[List[str]]) -> List[str]:
17.         
18.         from collections import defaultdict, deque
19.         ## 将机票数据转化为一个图的邻接表 即字典 并按字典序逆序存储目的地
20.         ticket_dict = defaultdict(list)
21.         for ticket_info in tickets:
22.             ticket_dict[ticket_info[0]].append(ticket_info[1])
23.         # print(ticket_dict)
25.         for depart in ticket_dict:
26.             ticket_dict[depart].sort(reverse = True)
27.         # print(ticket_dict)
28.         
29.         ## 用一个deque方便更清晰清晰描述算法逻辑
30.         results = deque()
31.         self.backtrack(ticket_dict, 'JFK', results)
33.         return list(results)

复制代码

51. N 皇后

要点：

n个皇后放置在n*n的棋盘，根据题意可知，同一行不可能存在两个皇后。因此遍历的次序就可以按行进行位置遍历，然后清除同列和斜线攻击的情况。如许就转换成了树形布局深度为n的嵌套循环的逻辑。收集所有情况就可以输出到结果。
解法：

输入输出：
1.传入当前棋盘（某节点），2.row_idx 和startidx类似，指定现在遍历的是第几行
这里的输出是将单个棋盘的情况转成了一维的字符串数组，现实上输出的构成是 棋盘*列*行的三维情势
单步逻辑：预定义一个函数来判断，输入一个坐标，它的行列斜线中（其实只需要检查上方，因为下方还没有填充）是否出现了其他皇后。假如合法，那么放入皇后，将放置过的结果带入下一轮回溯。
终止条件：放置完末了一个皇后输出。非法情况要在递归中过滤，防止重复处理
实现:

二维过程照旧比力轻易把列和行错位，最好把变量写清楚

1. class Solution:
3.     def is_valid(self, cb, row_idx, col_idx):
4.         
5.         # 同一列有皇后
6.         for row in cb:
7.             if row[col_idx] == 'Q':
8.                 return False
10.         # 左上有皇后
11.         i, j = row_idx - 1, col_idx - 1
12.         while i >= 0 and j >= 0:
13.             if cb[i][j] == 'Q':
14.                 return False
15.             i -= 1
16.             j -= 1
17.         
18.         # 右上有皇后
19.         i, j = row_idx - 1, col_idx + 1
20.         while i >= 0 and j < len(cb):
21.             if cb[i][j] == 'Q':
22.                 return False
23.             i -= 1
24.             j += 1
26.         return True
28.     def put_queen(self, row, i):
29.         return row[:i] + 'Q' + row[i+1:]
31.     def pop_queen(self, row, i):
32.         return row[:i] + '.' + row[i+1:]
34.     def backtrack(self, n, chess_board, row_idx, results):
35.         
36.         if row_idx == n:
37.             results.append(chess_board[:])
38.             return
40.         for col_idx in range(n):
41.             if self.is_valid(chess_board, row_idx, col_idx):
42.                 chess_board[row_idx] = self.put_queen(chess_board[row_idx], col_idx)
43.                 self.backtrack(n, chess_board, row_idx + 1, results)
44.                 chess_board[row_idx] = self.pop_queen(chess_board[row_idx], col_idx)
47.     def solveNQueens(self, n: int) -> List[List[str]]:
48.         
49.         chess_board = ['.' * n] * n
50.         results = list()
51.         self.backtrack(n, chess_board, 0, results)
53.         return results

复制代码

37. 解数独 

要点：

N皇后题目 (opens new window)是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来遍历列，然后一行一列确定皇后的唯一位置。
本题就不一样了，本题中棋盘的每一个位置都要放一个数字（而N皇后是一行只放一个皇后），并检查数字是否合法，解数独的树形布局要比N皇后更宽更深。
详细来说，N皇后题目只需要按行遍历即可，因为这是游戏规则决定的。但是数独每行都需要摆放多个数字；同时，还要满足3*3的小矩阵内没有重复。
因此这里是一个二维的回溯，比N皇后题目在外层多一层嵌套：一个for循环确定行，一个for循环确定列，然后进入递归，去判断这个格子应该放置哪个合法数字。
解法：

输入输出：1.输入当前棋盘，2.输入空格位置，3.根据棋盘判断可以或许填入的合法数字
终止条件：回溯利用bool值进行返回，一直填满终止
单步逻辑：1. 利用一个嵌套循环确定当前遍历位置，2. 判断当前位置是否已经有数字，假如照旧空，则利用一个预定义函数来确定当前位置可以填入的数字，3. 移动到下一个位置，进行后续的遍历。
实现：

可以发现树形布局是比力有规律的，要点在于：1. 利用清楚有效的预定义函数来判断待填入数字；2. 回溯部分利用bool类型返回，可以快速锁定正确的路径，
下面先展示一下现在可以ac的解法，由于测试例做了修改，利用朴素的递归加每个格点逐个判断会导致超时，因此，这里额外借助一个储存空间，同时每次优先办理可用数字最少的格子，资助我们减少暴力遍历整个大矩阵的次数：

1. class Solution:
2.     def solveSudoku(self, board: List[List[str]]) -> None:
3.         #初始化数据结构 记录每一行 每一列、每个小矩阵中已经填入的数字·
4.         rows  = [set() for _ in range(9)]
5.         cols  = [set() for _ in range(9)]
6.         boxes = [set() for _ in range(9)]
8.         ## 遍历一遍现有矩阵 存入已有的数字
9.         ## 这里存入了9行 9列 和9个小矩阵
10.         for r in range(9):
11.             for c in range(9):
12.                 if board[r][c] != '.':
13.                     num = board[r][c]
14.                     ## 对每个行列小矩阵进行一次赋值
15.                     rows[r].add(num)
16.                     cols[c].add(num)
17.                     ## 例如 4行5列 得到 3+1 index为4的小矩阵
18.                     box_index = (r//3)*3 + (c//3)
19.                     boxes[box_index].add(num)
21.         #找到下一个待填充的空格 启发式搜索
22.         def next_empty_cell():
23.             # 候选数字的数量最大是9个，初始化值大于最大可能值，避免边界问题
24.             min_options = 10
25.             # 候选数字最少的单元格坐标
26.             best_cell = None
27.             for r in range(9):
28.                 for c in range(9):
29.                     ## 如果是空白单元格 需要填数字
30.                     if board[r][c] == '.':
31.                         box_index = (r // 3) * 3 + c // 3
32.                         possible_numbers = set('123456789') - rows[r] - cols[c] - boxes[box_index]
33.                         ## 寻找可用数字最少的格子
34.                         if len(possible_numbers) < min_options:
35.                             min_options = len(possible_numbers)
36.                             best_cell = (r,c)
37.                             if min_options == 1:
38.                                 return best_cell
40.             return best_cell
43.         def backtracking():
45.             # 先找到一个候选数字最少的空单元格
46.             cell = next_empty_cell()
47.             # 如果已经没有空单元格说明找到了解决方案
48.             if not cell:
49.                 return True
50.             #计算候选数字
51.             r, c = cell
52.             box_index = (r // 3) * 3 + c //3
53.             possible_numbers = set('123456789') - rows[r] - cols[c] - boxes[box_index]
54.             #尝试候选数字
55.             for num in possible_numbers:
56.                 #更新棋盘和对应的数据结构
57.                 board[r][c] = num
58.                 rows[r].add(num)
59.                 cols[c].add(num)
60.                 boxes[box_index].add(num)
61.                 if backtracking():
62.                     return True
63.                 board[r][c] = '.'
64.                 rows[r].remove(num)
65.                 cols[c].remove(num)
66.                 boxes[box_index].remove(num)
67.             return False
68.             
69.         backtracking()

复制代码

第一种解法先提取了可以利用的数字进行递归，在已出现数字较少的情况下会超时：

1. from typing import List
3. class Solution:
4.     def valid_nums(self, row_idx, col_idx, board):
5.         ## 查找本行已经使用过的数字
6.         row_num = set(int(num) for num in board[row_idx] if num != '.')
7.         ## 查找本列已经使用过的数字
8.         col_num = set(int(board[i][col_idx]) for i in range(9) if board[i][col_idx] != '.')
9.         ## 查找小矩阵中已经使用过的数字
10.         mat_row_start = (row_idx // 3) * 3
11.         mat_col_start = (col_idx // 3) * 3
12.         mat_num = set()
13.         for i in range(mat_row_start, mat_row_start + 3):
14.             for j in range(mat_col_start, mat_col_start + 3):
15.                 if board[i][j] != '.':
16.                     mat_num.add(int(board[i][j]))
17.         ## 求矩阵并集
18.         exist_num_set = row_num | col_num | mat_num
19.         ## 求剩余有效的可用数字
20.         valid_num_set = set(range(1, 10)).difference(exist_num_set)
22.         return valid_num_set
24.     def back_track(self, board):
25.         for row_idx in range(9):
26.             for col_idx in range(9):
27.                 # 对已填充的格子不做处理
28.                 if board[row_idx][col_idx] != '.':
29.                     continue
31.                 # 提取可用数字
32.                 valid_num_set = self.valid_nums(row_idx, col_idx, board)
33.                 if not valid_num_set:
34.                     return False
36.                 # 对每个格子递归当前可用的数字
37.                 for num in valid_num_set:
38.                     board[row_idx][col_idx] = str(num)
39.                     if self.back_track(board):
40.                         return True
41.                         
42.                     # 清除当前数字以进行回溯
43.                     board[row_idx][col_idx] = '.'  
45.                 return False
46.         # 如果所有位置都填满，返回 True
47.         return True  
49.     def solveSudoku(self, board: List[List[str]]) -> None:
50.         self.back_track(board)
52.         

复制代码

直接对每个格子遍历1-9数字，不合法直接返回false来加速，仍然有一个测试例超时：

1. class Solution:
2.     def is_valid(self, row_idx, col_idx, board, n):
4.         ## 排除行相同
5.         for num in board[row_idx]:
6.             if n == num:
7.                 return False
9.         ## 排除列相同
10.         for i in range(9):
11.             if n == board[i][col_idx]:
12.                 return False
14.         ## 排除小矩阵相同
15.         mat_row_start = (row_idx // 3) * 3
16.         mat_col_start = (col_idx // 3) * 3
17.         for i in range(mat_row_start, mat_row_start + 3):
18.             for j in range(mat_col_start, mat_col_start + 3):
19.                 if n == board[i][j]:
20.                     return False
22.         return True
24.     def back_track(self, board):
25.         for row_idx in range(9):
26.             for col_idx in range(9):
27.                 # 对已填充的格子不做处理
28.                 if board[row_idx][col_idx] != '.':
29.                     continue
31.                 # 对每个格子递归当前可用的数字
32.                 for n in range(1, 10):
33.                     if self.is_valid(row_idx, col_idx, board, str(n)):
34.                         board[row_idx][col_idx] = str(n)
35.                         if self.back_track(board):
36.                             return True
37.                         board[row_idx][col_idx] = '.'  
39.                 return False
41.         # 如果所有位置都填满，返回 True
42.         return True  
44.     def solveSudoku(self, board: List[List[str]]) -> None:
45.         self.back_track(board)
47.         

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。