读PDF复习环节3
- 本博客的内容只是做一个大概的记录，整个PDF看下来，内容上是不如代码随想录网站上的文章全面的，并且PDF中有些地方的描述，是很让我疑惑的，在困扰我很久后，无意间发现，其网站上的讲解完全符合我的思路。这次看完这些PDF后，暂时一段时间内不会再看了，要复习还是依靠，代码随想录网站，视频，和我自己写的博客吧
- 回溯算法章节，这算是我掌握的还行的一个章节了。
- 组合
- 组合总和 III
- 电话号码的字母组合
- 组合总和
- 本题，代码随想录的剪枝策略是，排序之后加剪枝，可以，不符合条件直接跳出当层for循环了。
- 组合总和II
- 树层去重，used[i-1] = False 。树枝去重，used[i-1] = True .
- 分割回文串
- 复原IP地址
- 子集
- 求组合，就要用到 idx ，求排列，不需要 idx ， 而且本题不需要 used 数组，idx 已经成功控制了。
- 子集II
- 递增子序列
- 本题太具有迷惑性了，一开始还真没注意！本题给的示例都是排好序的，让我误以为可以使用之前的去重逻辑！实则不然，因为求的是递增子序列，这意味着我们不能对数组进行排序操作，所以不能使用之前的去重逻辑。要使用新的，在递归函数中每次都声明的，哈希(集合)去重逻辑，我不喜欢用set，我喜欢用哈希。
- 代码随想录的代码
- 全排列
- 求排列，不需要 idx , 递归中每次都是从0开始遍历，但要用used数组，来表示哪些元素已经被使用过。
- 全排列 II
- 小小去重，可笑可笑
- 但是这道题的去重很有意思，要去看代码随想录的解答。
- 回溯算法去重问题的另一种写法
- 可以看看，核心思想是，讲解树层去重和树枝去重。
- 重新安排行程
- 再看依旧是不会
- N皇后
- 前几天写过了，核心思想就是，皇后一定是一行一行放的，每行放一个，所以可以用一个idx来控制当前是第几行，只要for循环遍历每个列位置就可以了，另外，在判断皇后是否合法时，我们只需要知道每个皇后的位置就可以了，不需要传入整个棋盘，那样太复杂了。
- 数独
- 本题的要点在于，就是在每个递归函数中，都使用三层，从0开始遍历的for循环，遍历行，遍历列，遍历数字，利用棋盘中，该位置是否是空，来判断是否在该位置填入数字，这样的编程逻辑是非常自然的。如果是想用idx来控制当前输入到了第几行第几列，那样就太麻烦了！遇到数字就continue，多跑几次什么都不做的for循环是无所谓的！
- 同样，在上面的编写逻辑下，判断是否合法也是较为容易的，只需要传入当前参数，每层循环的 i j k ，去判断，同行，同列，同小块，是否合法即可。
本博客的内容只是做一个大概的记录，整个PDF看下来，内容上是不如代码随想录网站上的文章全面的，并且PDF中有些地方的描述，是很让我疑惑的，在困扰我很久后，无意间发现，其网站上的讲解完全符合我的思路。这次看完这些PDF后，暂时一段时间内不会再看了，要复习还是依靠，代码随想录网站，视频，和我自己写的博客吧
回溯算法章节，这算是我掌握的还行的一个章节了。
组合
其中使用的剪枝技巧值得学习。
组合总和 III
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
self.res = []
path = []
idx = 1
self.backtracking(k,n,idx,path)
return self.res
def backtracking(self,k,n,idx,path):
if len(path)==k :
if n == 0 :
self.res.append(path.copy())
return
else :
return
# 小小剪枝
for i in range(idx,10-(k-len(path))+1):
# 小小剪枝
if n-i < 0 :
continue
else :
path.append(i)
self.backtracking(k,n-i,i+1,path)
path.pop()
return
电话号码的字母组合
只要用 idx 来控制当前应该取第几个数字，就只需要一层循环了，而不是之前我习惯的两层循环。
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if digits == '' :
return []
self.dict = {'1' : '', '0' : '' , '#' : '' , '*' : '' ,
'2':'abc' , '3':'def' , '4':'ghi' , '5':'jkl', '6':'mno' ,
'7':'pqrs','8':'tuv','9':'wxyz'}
self.res = []
path = []
n = len(digits)
idx = 0
self.backtracking(digits,n,idx,path)
return self.res
def backtracking(self,digits,n,idx,path):
if len(path) == n :
self.res.append(''.join(path))
return
# 取当前的数字
number = digits[idx]
ss = self.dict[number]
m = len(ss)
# 在当前数字对应的字符串中，从0开始遍历
for i in range(m):
path.append(ss[i])
self.backtracking(digits,n,idx+1,path)
path.pop()
组合总和
本题需要注意的是，虽然元素可以重复，但是必须要有idx，idx是保证，遍历一直是正序的，不会走回头路。
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
self.res = []
path = []
n = len(candidates)
idx = 0
self.backtracking(candidates,n,target,idx,path)
return self.res
def backtracking(self,candidates,n,target,idx,path):
if target == 0 :
self.res.append(path.copy())
return
if target < 0 :
return
for i in range(idx,n):
if target < candidates[i] :
continue
path.append(candidates[i])
# 注意这里,传入 idx 的区别,因为元素可以重复，所以是 i , 不是 i+1
# 但是也必须要有idx !!!
self.backtracking(candidates,n,target-candidates[i],i,path)
path.pop()
本题，代码随想录的剪枝策略是，排序之后加剪枝，可以，不符合条件直接跳出当层for循环了。
class Solution:
def backtracking(self, candidates, target, total, startIndex, path, result):
if total == target:
result.append(path[:])
return
for i in range(startIndex, len(candidates)):
if total + candidates[i] > target:
break
total += candidates[i]
path.append(candidates[i])
self.backtracking(candidates, target, total, i, path, result)
total -= candidates[i]
path.pop()
def combinationSum(self, candidates, target):
result = []
candidates.sort() # 需要排序
self.backtracking(candidates, target, 0, 0, [], result)
return result
组合总和II
剪枝+used数组去重。
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
n = len(candidates)
self.res = []
path = []
used = [False]*n
idx = 0
self.backtracking(candidates,target,n,idx,path,used)
return self.res
def backtracking(self,candidates,target,n,idx,path,used):
if target == 0 :
self.res.append(path.copy())
return
if target < 0 :
return
for i in range(idx,n):
if candidates[i] > target :
break
if i > 0 and used[i-1] == False and candidates[i]==candidates[i-1]:
continue
path.append(candidates[i])
used[i] = True
self.backtracking(candidates,target-candidates[i],n,i+1,path,used)
used[i] = False
path.pop()
树层去重，used[i-1] = False 。树枝去重，used[i-1] = True .
代码随想录的代码
class Solution:
def backtracking(self, candidates, target, total, startIndex, used, path, result):
if total == target:
result.append(path[:])
return
for i in range(startIndex, len(candidates)):
# 对于相同的数字，只选择第一个未被使用的数字，跳过其他相同数字
if i > startIndex and candidates[i] == candidates[i - 1] and not used[i - 1]:
continue
if total + candidates[i] > target:
break
total += candidates[i]
path.append(candidates[i])
used[i] = True
self.backtracking(candidates, target, total, i + 1, used, path, result)
used[i] = False
total -= candidates[i]
path.pop()
def combinationSum2(self, candidates, target):
used = [False] * len(candidates)
result = []
candidates.sort()
self.backtracking(candidates, target, 0, 0, used, [], result)
return result
分割回文串
注意分割区间定义即可，左闭右闭。
class Solution:
def partition(self, s: str) -> List[List[str]]:
self.res = []
path = []
n = len(s)
idx = 0
self.backtracking(s,n,idx,path)
return self.res
def backtracking(self,s,n,idx,path):
if idx >= n :
self.res.append(path.copy())
return
# 这里注意细节就好，i就是要取到n-1
# 加入s='aa',s[1:2]='a'，索引下标，是不包括最后一个值的
for i in range(idx,n):
# 注意回文子串区间定义：[idx,i],i为分割线
temp = s[idx:i+1]
if self.is_right(temp):
path.append(temp)
self.backtracking(s,n,i+1,path)
path.pop()
def is_right(self,temp):
left = 0
right = len(temp)-1
while left < right :
if temp[left]!=temp[right]:
return False
left += 1
right -= 1
return True
还可以提前使用动态规划的方法，判断出给字符串的所有子串是否是回文串，然后将结果储存起来。核心代码就是，先从下到上遍历，再从左到右遍历，一共需要考虑三种情况，会导致 dp[i][j] 是回文串，dp[i][j] 代表字符串中 [i,j] 的子串，是不是回文串。
class Solution:
def partition(self, s: str) -> List[List[str]]:
result = []
isPalindrome = [[False] * len(s) for _ in range(len(s))] # 初始化isPalindrome矩阵
self.computePalindrome(s, isPalindrome)
self.backtracking(s, 0, [], result, isPalindrome)
return result
def backtracking(self, s, startIndex, path, result, isPalindrome):
if startIndex >= len(s):
result.append(path[:])
return
for i in range(startIndex, len(s)):
if isPalindrome[startIndex][i]: # 是回文子串
substring = s[startIndex:i + 1]
path.append(substring)
self.backtracking(s, i + 1, path, result, isPalindrome) # 寻找i+1为起始位置的子串
path.pop() # 回溯过程，弹出本次已经添加的子串
def computePalindrome(self, s, isPalindrome):
for i in range(len(s) - 1, -1, -1): # 需要倒序计算，保证在i行时，i+1行已经计算好了
for j in range(i, len(s)):
if j == i:
isPalindrome[i][j] = True
elif j - i == 1:
isPalindrome[i][j] = (s[i] == s[j])
else:
isPalindrome[i][j] = (s[i] == s[j] and isPalindrome[i+1][j-1])
复原IP地址
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
self.res = []
path = []
idx = 0
n = len(s)
self.backtacking(s,n,idx,path)
return self.res
def backtacking(self,s,n,idx,path):
if idx >= n :
if len(path)==4:
self.res.append('.'.join(path))
return
else :
return
if len(path)==3 :
temp = s[idx:n]
if self.is_right(temp):
path.append(temp)
self.backtacking(s,n,n,path)
path.pop()
else :
for i in range(idx,n):
temp = s[idx:i+1]
if self.is_right(temp):
path.append(temp)
self.backtacking(s,n,i+1,path)
path.pop()
def is_right(self,temp):
n = len(temp)
if temp[0] == '0' and n > 1 :
return False
if int(temp) > 255 or int(temp) < 0 :
return False
return True
我觉得我还剪了一下枝，挺好，
代码随想录的代码：
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
results = []
self.backtracking(s, 0, [], results)
return results
def backtracking(self, s, index, path, results):
if index == len(s) and len(path) == 4:
results.append('.'.join(path))
return
if len(path) > 4: # 剪枝
return
for i in range(index, min(index + 3, len(s))):
if self.is_valid(s, index, i):
sub = s[index:i+1]
path.append(sub)
self.backtracking(s, i+1, path, results)
path.pop()
def is_valid(self, s, start, end):
if start > end:
return False
if s[start] == '0' and start != end: # 0开头的数字不合法
return False
num = int(s[start:end+1])
return 0 <= num <= 255
子集
冗余的代码，本题不需要 used 数组，idx 已经可以控制，不出现重复了。
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
self.res = []
path = []
n = len(nums)
used = [False]*n
idx = 0
self.backtracking(nums,n,idx,used,path)
return self.res
def backtracking(self,nums,n,idx,used,path):
self.res.append(path.copy())
# 本题还是要有idx
for i in range(idx,n):
if used[i]==False :
used[i]=True
path.append(nums[i])
self.backtracking(nums,n,i+1,used,path)
path.pop()
used[i]=False
求组合，就要用到 idx ，求排列，不需要 idx ， 而且本题不需要 used 数组，idx 已经成功控制了。
代码随想录的代码：
class Solution:
def subsets(self, nums):
result = []
path = []
self.backtracking(nums, 0, path, result)
return result
def backtracking(self, nums, startIndex, path, result):
result.append(path[:]) # 收集子集，要放在终止添加的上面，否则会漏掉自己
# if startIndex >= len(nums): # 终止条件可以不加
# return
for i in range(startIndex, len(nums)):
path.append(nums[i])
self.backtracking(nums, i + 1, path, result)
path.pop()
子集II
直接套用之前的去重逻辑。
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
self.res = []
path = []
nums.sort()
n = len(nums)
used = [False]*n
idx = 0
self.backtracking(nums,n,idx,used,path)
return self.res
def backtracking(self,nums,n,idx,used,path):
self.res.append(path.copy())
# 本题还是要有idx
for i in range(idx,n):
if i > 0 and used[i-1]==False and nums[i-1]==nums[i]:
continue
else:
used[i]=True
path.append(nums[i])
self.backtracking(nums,n,i+1,used,path)
path.pop()
used[i]=False
递增子序列
本题太具有迷惑性了，一开始还真没注意！本题给的示例都是排好序的，让我误以为可以使用之前的去重逻辑！实则不然，因为求的是递增子序列，这意味着我们不能对数组进行排序操作，所以不能使用之前的去重逻辑。要使用新的，在递归函数中每次都声明的，哈希(集合)去重逻辑，我不喜欢用set，我喜欢用哈希。
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
self.res = []
path = []
idx = 0
n = len(nums)
self.backtracking(nums,n,idx,path)
return self.res
def backtracking(self,nums,n,idx,path):
if len(path)>=2:
self.res.append(path.copy())
used = [False]*201
for i in range(idx,n):
if used[100+nums[i]] == True:
continue
if path==[] or nums[i] >= path[-1] :
path.append(nums[i])
used[100+nums[i]] = True
self.backtracking(nums,n,i+1,path)
path.pop()
代码随想录的代码
递增子序列
class Solution:
def findSubsequences(self, nums):
result = []
path = []
self.backtracking(nums, 0, path, result)
return result
def backtracking(self, nums, startIndex, path, result):
if len(path) > 1:
result.append(path[:]) # 注意要使用切片将当前路径的副本加入结果集
# 注意这里不要加return，要取树上的节点
uset = set() # 使用集合对本层元素进行去重
for i in range(startIndex, len(nums)):
if (path and nums[i] < path[-1]) or nums[i] in uset:
continue
uset.add(nums[i]) # 记录这个元素在本层用过了，本层后面不能再用了
path.append(nums[i])
self.backtracking(nums, i + 1, path, result)
path.pop()
class Solution:
def findSubsequences(self, nums):
result = []
path = []
self.backtracking(nums, 0, path, result)
return result
def backtracking(self, nums, startIndex, path, result):
if len(path) > 1:
result.append(path[:]) # 注意要使用切片将当前路径的副本加入结果集
used = [0] * 201 # 使用数组来进行去重操作，题目说数值范围[-100, 100]
for i in range(startIndex, len(nums)):
if (path and nums[i] < path[-1]) or used[nums[i] + 100] == 1:
continue # 如果当前元素小于上一个元素，或者已经使用过当前元素，则跳过当前元素
used[nums[i] + 100] = 1 # 标记当前元素已经使用过
path.append(nums[i]) # 将当前元素加入当前递增子序列
self.backtracking(nums, i + 1, path, result)
path.pop()
全排列
求排列，不需要 idx , 递归中每次都是从0开始遍历，但要用used数组，来表示哪些元素已经被使用过。
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
self.res = []
path = []
n = len(nums)
used = [False]*n
self.backtracking(nums,n,used,path)
return self.res
def backtracking(self,nums,n,used,path):
if len(path)==n:
self.res.append(path.copy())
return
for i in range(n):
if used[i]==False :
used[i]=True
path.append(nums[i])
self.backtracking(nums,n,used,path)
path.pop()
used[i]=False
全排列 II
小小去重，可笑可笑
lass Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
self.res = []
path = []
n = len(nums)
nums.sort()
used = [False]*n
self.backtracking(nums,n,used,path)
return self.res
def backtracking(self,nums,n,used,path):
if len(path)==n:
self.res.append(path.copy())
return
for i in range(n):
if i > 0 and used[i-1] == False and nums[i-1]==nums[i]:
continue
if used[i]==False:
used[i]=True
path.append(nums[i])
self.backtracking(nums,n,used,path)
path.pop()
used[i]=False
但是这道题的去重很有意思，要去看代码随想录的解答。
全排列 II
回溯算法去重问题的另一种写法
可以看看，核心思想是，讲解树层去重和树枝去重。
回溯算法去重问题的另一种写法
重新安排行程
再看依旧是不会
重新安排行程
class Solution:
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
tickets.sort() # 先排序，这样一旦找到第一个可行路径，一定是字母排序最小的
used = [0] * len(tickets)
path = ['JFK']
results = []
self.backtracking(tickets, used, path, 'JFK', results)
return results[0]
def backtracking(self, tickets, used, path, cur, results):
if len(path) == len(tickets) + 1: # 终止条件：路径长度等于机票数量+1
results.append(path[:]) # 将当前路径添加到结果列表
return True
for i, ticket in enumerate(tickets): # 遍历机票列表
if ticket[0] == cur and used[i] == 0: # 找到起始机场为cur且未使用过的机票
used[i] = 1 # 标记该机票为已使用
path.append(ticket[1]) # 将到达机场添加到路径中
state = self.backtracking(tickets, used, path, ticket[1], results) # 递归搜索
path.pop() # 回溯，移除最后添加的到达机场
used[i] = 0 # 标记该机票为未使用
if state:
return True # 只要找到一个可行路径就返回，不继续搜索
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() # 对目的地列表进行排序
path = ["JFK"] # 起始机场为"JFK"
self.backtracking(targets, path, len(tickets))
return path
def backtracking(self, targets, path, ticketNum):
if len(path) == ticketNum + 1:
return True # 找到有效行程
airport = path[-1] # 当前机场
destinations = targets[airport] # 当前机场可以到达的目的地列表
for i, dest in enumerate(destinations):
targets[airport].pop(i) # 标记已使用的机票
path.append(dest) # 添加目的地到路径
if self.backtracking(targets, path, ticketNum):
return True # 找到有效行程
targets[airport].insert(i, dest) # 回溯，恢复机票
path.pop() # 移除目的地
return False # 没有找到有效行程
N皇后
前几天写过了，核心思想就是，皇后一定是一行一行放的，每行放一个，所以可以用一个idx来控制当前是第几行，只要for循环遍历每个列位置就可以了，另外，在判断皇后是否合法时，我们只需要知道每个皇后的位置就可以了，不需要传入整个棋盘，那样太复杂了。
代码随想录的代码：
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[:]) # 棋盘填满，将当前解加入结果集
return
for 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 - 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 # 当前位置合法
数独
本题的要点在于，就是在每个递归函数中，都使用三层，从0开始遍历的for循环，遍历行，遍历列，遍历数字，利用棋盘中，该位置是否是空，来判断是否在该位置填入数字，这样的编程逻辑是非常自然的。如果是想用idx来控制当前输入到了第几行第几列，那样就太麻烦了！遇到数字就continue，多跑几次什么都不做的for循环是无所谓的！
同样，在上面的编写逻辑下，判断是否合法也是较为容易的，只需要传入当前参数，每层循环的 i j k ，去判断，同行，同列，同小块，是否合法即可。
代码随想录的代码：
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；若无解，返回False
for i in range(len(board)): # 遍历行
for j in range(len(board[0])): # 遍历列
# 若空格内已有数字，跳过
if board[i][j] != '.': continue
for k in range(1, 10):
if self.is_valid(i, j, k, board):
board[i][j] = str(k)
if self.backtracking(board): return True
board[i][j] = '.'
# 若数字1-9都不能成功填入空格，返回False无解
return False
return 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) * 3
start_col = (col // 3) * 3
for i in range(start_row, start_row + 3):
for j in range(start_col, start_col + 3):
if board[i][j] == str(val):
return False
return True
