读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 = 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