温州网站建设的公司,云浮网站建设咨询,网站建设 微盘下载,国外虚拟物品交易网站读PDF复习环节3 本博客的内容只是做一个大概的记录#xff0c;整个PDF看下来#xff0c;内容上是不如代码随想录网站上的文章全面的#xff0c;并且PDF中有些地方的描述#xff0c;是很让我疑惑的#xff0c;在困扰我很久后#xff0c;无意间发现#xff0c;其网站上的讲… 读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,i1,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,idx1,path)path.pop()
组合总和
本题需要注意的是虽然元素可以重复但是必须要有idxidx是保证遍历一直是正序的不会走回头路。
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 , 不是 i1# 但是也必须要有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,i1,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# 加入saa,s[1:2]a索引下标是不包括最后一个值的for i in range(idx,n):# 注意回文子串区间定义[idx,i],i为分割线temp s[idx:i1]if self.is_right(temp):path.append(temp)self.backtracking(s,n,i1,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) # 寻找i1为起始位置的子串path.pop() # 回溯过程弹出本次已经添加的子串def computePalindrome(self, s, isPalindrome):for i in range(len(s) - 1, -1, -1): # 需要倒序计算保证在i行时i1行已经计算好了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[i1][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:i1]if self.is_right(temp):path.append(temp)self.backtacking(s,n,i1,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:i1]path.append(sub)self.backtracking(s, i1, 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:end1])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,i1,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,i1,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[100nums[i]] True:continueif path[] or nums[i] path[-1] :path.append(nums[i])used[100nums[i]] Trueself.backtracking(nums,n,i1,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] # 起始机场为JFKself.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][col1:] # 放置皇后self.backtracking(n, row 1, chessboard, result) # 递归到下一行chessboard[row] chessboard[row][:col] . chessboard[row][col1:] # 回溯撤销当前位置的皇后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
