代码随想录算法训练营第二十五天 | 读PDF复习环节3

本博客的内容只是做一个大概的记录，整个PDF看下来，内容上是不如代码随想录网站上的文章全面的，并且PDF中有些地方的描述，是很让我疑惑的，在困扰我很久后，无意间发现，其网站上的讲解完全符合我的思路。这次看完这些PDF后，暂时一段时间内不会再看了，要复习还是依靠，代码随想录网站，视频，和我自己写的博客吧

回溯算法章节，这算是我掌握的还行的一个章节了。

组合

其中使用的剪枝技巧值得学习。

组合总和 III

class Solution:def combinationSum3(self, k: int, n: int) -> List[List[int]]:self.res = []path = []idx = 1self.backtracking(k,n,idx,path)return self.resdef backtracking(self,k,n,idx,path):if len(path)==k :if n == 0 :self.res.append(path.copy())returnelse :return# 小小剪枝for i in range(idx,10-(k-len(path))+1):# 小小剪枝if n-i < 0 :continueelse :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 = 0self.backtracking(digits,n,idx,path)return self.resdef 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 = 0self.backtracking(candidates,n,target,idx,path)return self.resdef backtracking(self,candidates,n,target,idx,path):if target == 0 :self.res.append(path.copy())returnif target < 0 :returnfor i in range(idx,n):if target < candidates[i] :continuepath.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[:])returnfor i in range(startIndex, len(candidates)):if total + candidates[i] > target:breaktotal += 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]*nidx = 0self.backtracking(candidates,target,n,idx,path,used)return self.resdef backtracking(self,candidates,target,n,idx,path,used):if target == 0 :self.res.append(path.copy())returnif target < 0 :return for i in range(idx,n):if candidates[i] > target :breakif i > 0 and used[i-1] == False and candidates[i]==candidates[i-1]:continuepath.append(candidates[i])used[i] = Trueself.backtracking(candidates,target-candidates[i],n,i+1,path,used)used[i] = Falsepath.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[:])returnfor i in range(startIndex, len(candidates)):# 对于相同的数字，只选择第一个未被使用的数字，跳过其他相同数字if i > startIndex and candidates[i] == candidates[i - 1] and not used[i - 1]:continueif total + candidates[i] > target:breaktotal += candidates[i]path.append(candidates[i])used[i] = Trueself.backtracking(candidates, target, total, i + 1, used, path, result)used[i] = Falsetotal -= 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 = 0self.backtracking(s,n,idx,path)return self.resdef 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 = 0right = len(temp)-1while left < right :if temp[left]!=temp[right]:return Falseleft += 1right -= 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 resultdef backtracking(self, s, startIndex, path, result, isPalindrome):if startIndex >= len(s):result.append(path[:])returnfor 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] = Trueelif 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 = 0n = len(s)self.backtacking(s,n,idx,path)return self.resdef backtacking(self,s,n,idx,path):if idx >= n :if len(path)==4:self.res.append('.'.join(path))returnelse :returnif 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 Falseif int(temp) > 255 or int(temp) < 0 :return Falsereturn True

我觉得我还剪了一下枝，挺好，

代码随想录的代码：

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:results = []self.backtracking(s, 0, [], results)return resultsdef backtracking(self, s, index, path, results):if index == len(s) and len(path) == 4:results.append('.'.join(path))returnif len(path) > 4:  # 剪枝returnfor 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 Falseif s[start] == '0' and start != end:  # 0开头的数字不合法return Falsenum = 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]*nidx = 0self.backtracking(nums,n,idx,used,path)return self.resdef backtracking(self,nums,n,idx,used,path):self.res.append(path.copy())# 本题还是要有idxfor i in range(idx,n):if used[i]==False :used[i]=Truepath.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 resultdef backtracking(self, nums, startIndex, path, result):result.append(path[:])  # 收集子集，要放在终止添加的上面，否则会漏掉自己# if startIndex >= len(nums):  # 终止条件可以不加#     returnfor 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]*nidx = 0self.backtracking(nums,n,idx,used,path)return self.resdef backtracking(self,nums,n,idx,used,path):self.res.append(path.copy())# 本题还是要有idxfor i in range(idx,n):if i > 0 and used[i-1]==False and nums[i-1]==nums[i]:continueelse:   used[i]=Truepath.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 = 0n = len(nums)self.backtracking(nums,n,idx,path)return self.resdef backtracking(self,nums,n,idx,path):if len(path)>=2:self.res.append(path.copy())used = [False]*201for i in range(idx,n):if used[100+nums[i]] == True:continueif path==[] or nums[i] >= path[-1] :path.append(nums[i])used[100+nums[i]] = Trueself.backtracking(nums,n,i+1,path)path.pop()

代码随想录的代码

递增子序列

class Solution:def findSubsequences(self, nums):result = []path = []self.backtracking(nums, 0, path, result)return resultdef 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:continueuset.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 resultdef 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]*nself.backtracking(nums,n,used,path)return self.resdef backtracking(self,nums,n,used,path):if len(path)==n:self.res.append(path.copy())returnfor i in range(n):if used[i]==False :used[i]=Truepath.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]*nself.backtracking(nums,n,used,path)return self.resdef backtracking(self,nums,n,used,path):if len(path)==n:self.res.append(path.copy())returnfor i in range(n):if i > 0 and used[i-1] == False and nums[i-1]==nums[i]:continueif used[i]==False:used[i]=Truepath.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:  # 终止条件：路径长度等于机票数量+1results.append(path[:])  # 将当前路径添加到结果列表return Truefor 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 defaultdictclass 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 pathdef 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[:])  # 棋盘填满，将当前解加入结果集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  # 当前位置合法

数独

本题的要点在于，就是在每个递归函数中，都使用三层，从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；若无解，返回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