ToB企服应用市场:ToB评测及商务社交产业平台

标题: 代码随想录D24-25 回溯算法03-04 Python [打印本页]

作者: 风雨同行 时间: 2024-12-23 09:10
标题: 代码随想录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。这是递归的单层逻辑。
实现：

class Solution:
## 根据规则预定义一个判断函数判断每段截取的字段是否合规
def is_valid(self, s, start, end):
if start > end:
return False
# 0开头且长度大于1的数字不合法
if s[start] == '0' and start != end:
return False
num = int(s[start:end+1])
return 0 <= num <= 255
def backtrack(self, s, start_idx, path, results):
## 判断数组长度和start_idx指向的位置决定是否返回
if len(path) == 4 and start_idx == len(s):
results.append('.'.join(path))
return
elif len(path) > 4:
return
## 指定i的边界防止最后一位索引出界
for i in range(start_idx, min(start_idx + 3, len(s))):
if self.is_valid(s, start_idx, i):
part_str = s[start_idx: i + 1]
path.append(part_str)
self.backtrack(s, i + 1, path, results)
path.pop()
def restoreIpAddresses(self, s: str) -> List[str]:
results = list()
self.backtrack(s, 0, [], results)
return results

复制代码

78. 子集

要点子集题目：

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

解法：

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

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

复制代码

90. 子集 II

要点：

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

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

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

class Solution:
def backtrack(self, nums, used, start_idx, path, results):
results.append(path[:])
for i in range(start_idx, len(nums)):
if i > 0 and nums[i] == nums[i - 1] and used[i - 1] == 0:
continue
path.append(nums[i])
used[i] = 1
self.backtrack(nums, used, i + 1, path, results)
used[i] = 0
path.pop()
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums)
path, results = list(), list()
used = [0] * len(nums)
self.backtrack(nums, used, 0, path, results)
return results

复制代码

491. 非递减子序列

要点：

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

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

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

class Solution:
def backtrack(self, nums, start_idx, path, results):
if len(path) > 1:
results.append(path[:])
used = set()
for i in range(start_idx, len(nums)):
if (nums[i] in used) or (len(path) > 0 and nums[i] < path[-1]):
continue
used.add(nums[i])
path.append(nums[i])
self.backtrack(nums, i + 1, path, results)
path.pop()
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
path, results = list(), list()
self.backtrack(nums, 0, path, results)
return results

复制代码

46. 全分列

要点：

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

解法：

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

class Solution:
def backtrack(self, nums, used, path, results):
if len(path) == len(nums):
results.append(path[:])
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
self.backtrack(nums, used, path, results)
path.pop()
used[i] = False
def permute(self, nums: List[int]) -> List[List[int]]:
used = [False] * len(nums)
path, results = list(), list()
self.backtrack(nums, used, path, results)
return results

复制代码

47. 全分列 II

要点：

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

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

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

class Solution:
def backtrack(self, nums, used, path, results):
if len(path) == len(nums):
results.append(path[:])
for i in range(len(nums)):
## 通过两个条件过滤掉两种可能的重复
if (i > 0 and used[i - 1] == 0 and nums[i] == nums[i - 1]) or used[i] == 1:
continue
path.append(nums[i])
used[i] = 1
self.backtrack(nums, used, path, results)
used[i] = 0
path.pop()
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums)
used = [0] * len(nums)
path, results = list(), list()
self.backtrack(nums, used, path, results)
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弹出优先的目的地，题意包管了这条路线是可以探索到底的；
将目的地作为新的出发点继续遍历，出递归后输出结果。
实现：

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

复制代码

51. N 皇后

要点：

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

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

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

class Solution:
def is_valid(self, cb, row_idx, col_idx):
# 同一列有皇后
for row in cb:
if row[col_idx] == 'Q':
return False
# 左上有皇后
i, j = row_idx - 1, col_idx - 1
while i >= 0 and j >= 0:
if cb[i][j] == 'Q':
return False
i -= 1
j -= 1
# 右上有皇后
i, j = row_idx - 1, col_idx + 1
while i >= 0 and j < len(cb):
if cb[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def put_queen(self, row, i):
return row[:i] + 'Q' + row[i+1:]
def pop_queen(self, row, i):
return row[:i] + '.' + row[i+1:]
def backtrack(self, n, chess_board, row_idx, results):
if row_idx == n:
results.append(chess_board[:])
return
for col_idx in range(n):
if self.is_valid(chess_board, row_idx, col_idx):
chess_board[row_idx] = self.put_queen(chess_board[row_idx], col_idx)
self.backtrack(n, chess_board, row_idx + 1, results)
chess_board[row_idx] = self.pop_queen(chess_board[row_idx], col_idx)
def solveNQueens(self, n: int) -> List[List[str]]:
chess_board = ['.' * n] * n
results = list()
self.backtrack(n, chess_board, 0, results)
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的解法，由于测试例做了修改，利用朴素的递归加每个格点逐个判断会导致超时，因此，这里额外借助一个储存空间，同时每次优先办理可用数字最少的格子，资助我们减少暴力遍历整个大矩阵的次数：

class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
#初始化数据结构记录每一行每一列、每个小矩阵中已经填入的数字·
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
## 遍历一遍现有矩阵存入已有的数字
## 这里存入了9行 9列和9个小矩阵
for r in range(9):
for c in range(9):
if board[r][c] != '.':
num = board[r][c]
## 对每个行列小矩阵进行一次赋值
rows[r].add(num)
cols[c].add(num)
## 例如 4行5列得到 3+1 index为4的小矩阵
box_index = (r//3)*3 + (c//3)
boxes[box_index].add(num)
#找到下一个待填充的空格启发式搜索
def next_empty_cell():
# 候选数字的数量最大是9个，初始化值大于最大可能值，避免边界问题
min_options = 10
# 候选数字最少的单元格坐标
best_cell = None
for r in range(9):
for c in range(9):
## 如果是空白单元格需要填数字
if board[r][c] == '.':
box_index = (r // 3) * 3 + c // 3
possible_numbers = set('123456789') - rows[r] - cols[c] - boxes[box_index]
## 寻找可用数字最少的格子
if len(possible_numbers) < min_options:
min_options = len(possible_numbers)
best_cell = (r,c)
if min_options == 1:
return best_cell
return best_cell
def backtracking():
# 先找到一个候选数字最少的空单元格
cell = next_empty_cell()
# 如果已经没有空单元格说明找到了解决方案
if not cell:
return True
#计算候选数字
r, c = cell
box_index = (r // 3) * 3 + c //3
possible_numbers = set('123456789') - rows[r] - cols[c] - boxes[box_index]
#尝试候选数字
for num in possible_numbers:
#更新棋盘和对应的数据结构
board[r][c] = num
rows[r].add(num)
cols[c].add(num)
boxes[box_index].add(num)
if backtracking():
return True
board[r][c] = '.'
rows[r].remove(num)
cols[c].remove(num)
boxes[box_index].remove(num)
return False
backtracking()

复制代码

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

from typing import List
class Solution:
def valid_nums(self, row_idx, col_idx, board):
## 查找本行已经使用过的数字
row_num = set(int(num) for num in board[row_idx] if num != '.')
## 查找本列已经使用过的数字
col_num = set(int(board[i][col_idx]) for i in range(9) if board[i][col_idx] != '.')
## 查找小矩阵中已经使用过的数字
mat_row_start = (row_idx // 3) * 3
mat_col_start = (col_idx // 3) * 3
mat_num = set()
for i in range(mat_row_start, mat_row_start + 3):
for j in range(mat_col_start, mat_col_start + 3):
if board[i][j] != '.':
mat_num.add(int(board[i][j]))
## 求矩阵并集
exist_num_set = row_num | col_num | mat_num
## 求剩余有效的可用数字
valid_num_set = set(range(1, 10)).difference(exist_num_set)
return valid_num_set
def back_track(self, board):
for row_idx in range(9):
for col_idx in range(9):
# 对已填充的格子不做处理
if board[row_idx][col_idx] != '.':
continue
# 提取可用数字
valid_num_set = self.valid_nums(row_idx, col_idx, board)
if not valid_num_set:
return False
# 对每个格子递归当前可用的数字
for num in valid_num_set:
board[row_idx][col_idx] = str(num)
if self.back_track(board):
return True
# 清除当前数字以进行回溯
board[row_idx][col_idx] = '.'
return False
# 如果所有位置都填满，返回 True
return True
def solveSudoku(self, board: List[List[str]]) -> None:
self.back_track(board)

复制代码

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

class Solution:
def is_valid(self, row_idx, col_idx, board, n):
## 排除行相同
for num in board[row_idx]:
if n == num:
return False
## 排除列相同
for i in range(9):
if n == board[i][col_idx]:
return False
## 排除小矩阵相同
mat_row_start = (row_idx // 3) * 3
mat_col_start = (col_idx // 3) * 3
for i in range(mat_row_start, mat_row_start + 3):
for j in range(mat_col_start, mat_col_start + 3):
if n == board[i][j]:
return False
return True
def back_track(self, board):
for row_idx in range(9):
for col_idx in range(9):
# 对已填充的格子不做处理
if board[row_idx][col_idx] != '.':
continue
# 对每个格子递归当前可用的数字
for n in range(1, 10):
if self.is_valid(row_idx, col_idx, board, str(n)):
board[row_idx][col_idx] = str(n)
if self.back_track(board):
return True
board[row_idx][col_idx] = '.'
return False
# 如果所有位置都填满，返回 True
return True
def solveSudoku(self, board: List[List[str]]) -> None:
self.back_track(board)

复制代码

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

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)