引流用的电影网站怎么做,白城网站建设哪家专业,营销网站的特征,ui自学网站1.回溯算法 文章目录 1.回溯算法写在前面1.1回溯算法基本知识1.2组合问题1.3组合问题的剪枝操作1.4组合总和III1.5电话号码的字母组合1.6组合总和1.7组合总和II1.8分割回文串1.9复原IP地址1.10子集问题1.11子集II1.12非递减子序列1.13全排列1.14全排列II1.15N皇后1.16解数独 写…1.回溯算法 文章目录 1.回溯算法写在前面1.1回溯算法基本知识1.2组合问题1.3组合问题的剪枝操作1.4组合总和III1.5电话号码的字母组合1.6组合总和1.7组合总和II1.8分割回文串1.9复原IP地址1.10子集问题1.11子集II1.12非递减子序列1.13全排列1.14全排列II1.15N皇后1.16解数独 写在前面
本系列笔记主要作为笔者刷题的题解所用的语言为Python3若于您有助不胜荣幸。
1.1回溯算法基本知识
回溯算法也叫回溯搜索法是一种搜索方法回溯算法虽然难以理解但是其并不高效因为回溯的本质是穷举穷举所有的可能然后限制条件获得我们的想要的结果。想要回溯算法高效一点可以添加一些剪枝的操作但是这并不能改变回溯算法的本质。
回溯算法一般用于解决以下的问题
组合问题N个数里面按照一定规则找出k个数的集合切割问题一个字符串按照一定规则有几种切割方式子集问题一个N个数的集合里有多少种符合条件的子集排列问题N个数按照一定规则全排列有多少种排列方式棋盘问题N皇后解数独等。
回溯算法一般具有以下的模板
回溯函数模板返回值及参数
回溯算法中函数的返回值一般为空None回溯算法的参数不会像二叉树递归那样容易确定一般是先写逻辑然后需要什么参数的时候再进行修改。
回溯函数的函数定义一般如下
def backtracking(参数) - None:回溯函数的终止条件
回溯函数一定是树形结构的所有一定有终止条件满足一定的终止条件的时候我们就应该进行返回了一般是我们遇到叶子节点的时候这时候就要收集结果了所以回溯函数终止条件的伪代码如下
if 终止条件:存放结果return回溯搜索的遍历过程
回溯法一般是再集合中递归搜索集合的大小构成了树的宽度递归的深度构成了树的深度。
回溯函数遍历过程伪代码如下
for 选择本层集合中元素:处理节点backtracking(路径, 选择列表)回溯撤销处理结果所以回溯法的整体结构如下
def backtracking(参数) - None:if 终止条件:存放结果returnfor 选择本层集合中元素树中节点孩子的数量就是集合的大小:处理节点backtracking(路径, 选择列表) # 递归回溯撤销处理结果回溯算法相当于是递归算法里面还嵌套了for循环。
1.2组合问题
77. 组合
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
思路中说到回溯法解决的问题都可以抽象为树形结构N叉树用树形结构来理解回溯就容易多了我们可以将回溯算法抽象成下列的一个二叉树当我们在叶子节点的时候我们就可以收获结果了就得到了所有的组合。 如何确定终止条件呢遇到叶子节点的时候就终止了其实这个时候我们用于保存中间结果的path的长度为k所以我们可以进行判断if len(path) k:如果满足条件则遇到叶子节点可以保存结果。
class Solution:def __init__(self):self.res: List[List[int]] []self.path: List[int] []def backtracking(self, n: int, k: int, startIndex: int) - None:if len(self.path) k: # 终止条件收获结果self.res.append(self.path[:]) # 这里需要进行copyreturnfor i in range(startIndex, n): # 循环遍历self.path.append(i1)self.backtracking(n, k, i1)self.path.pop()def combine(self, n: int, k: int) - List[List[int]]:self.backtracking(n, k, 0)return self.res1.3组合问题的剪枝操作
77. 组合
给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
思路回溯算法的剪枝一般是在回溯搜索的过程中进行的来举一个例子n 4k 4的话那么第一层for循环的时候从元素2开始的遍历都没有意义了。 在第二层for循环从元素3开始的遍历都没有意义了。 所以可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
这个剪枝的条件可以则么看
当前已经选择的元素个数为len(self.path)还需要选择的元素个数为k-len(self.path)列表中剩余元素的个数为(n-i)剩余元素的个数一定要大于等于所需要的元素的个数即(n-i) k - len(self.path)则有i n-(k-len(self.size))这里由于range()函数是一个左闭右开的函数所以我们这里的值应该设为range(startIndex, n-(k-len(self.path))1)。
class Solution:def __init__(self):self.path: List[int] []self.res: List[List[int]] []def backtracking(self, n: int, k: int, startIndex: int) - None:if len(self.path) k:self.res.append(self.path[:])return for i in range(startIndex, n-(k-len(self.path))1): # 剪枝操作self.path.append(i1)self.backtracking(n, k, i1)self.path.pop()def combine(self, n: int, k: int) - List[List[int]]:self.backtracking(n, k, 0)return self.res1.4组合总和III
216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合且满足下列条件
只使用数字1到9每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
思路k控制树的深度而n控制树的宽度 class Solution:def __init__(self):self.path: List[int] []self.res: List[List[int]] []def backtracking(self, targetSum: int, Sum: int, k: int, startIndex: int) - None:if len(self.path) k: # 终止条件if Sum targetSum: # 收获结果self.res.append(self.path[:])returnfor i in range(startIndex, 9-(k-len(self.path))1): # 循环遍历,进行剪枝限制至少有k个元素self.path.append(i1)self.backtracking(targetSum, Sumi1, k, i1) # 显式回溯self.path.pop()def combinationSum3(self, k: int, n: int) - List[List[int]]:self.backtracking(n, 0, k, 0)return self.res1.5电话号码的字母组合
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 1 1 1 2 a b c 2_{abc} 2abc 3 d e f 3_{def} 3def 4 g h i 4_{ghi} 4ghi 5 j k l 5_{jkl} 5jkl 6 m n o 6_{mno} 6mno 7 p q r s 7_{pqrs} 7pqrs 8 t u v 8_{tuv} 8tuv 9 w x y z 9_{wxyz} 9wxyz ∗ * ∗ 0 0 0#
思路我们这里遍历的是两个集合所以不需要startIndex来去重但是需要一个index来指向当前遍历的数字
解法一使用list来保存结果
class Solution:def __init__(self):self.str_map: List[str] [, # 0, # 1abc, # 2def, # 3ghi, # 4jkl, # 5mno, # 6pqrs, # 7tuv, # 8wxyz # 9]self.res: List[str] []self.path: List[str] []def backtracking(self, digits: str, index: int) - None:if index len(digits):self.res.append(.join(self.path))returnletters: str self.str_map[int(digits[index])]for char in letters:self.path.append(char)self.backtracking(digits, index1)self.path.pop()def letterCombinations(self, digits: str) - List[str]:if not digits:return []self.backtracking(digits, 0)return self.res解法二精简回溯将s作为参数
class Solution:def __init__(self):self.str_map: List[str] [, # 0, # 1abc, # 2def, # 3ghi, # 4jkl, # 5mno, # 6pqrs, # 7tuv, # 8wxyz # 9]self.res: List[str] []def backtracking(self, digits: str, index: int, s: str) - None:if index len(digits):self.res.append(s)returnletters: str self.str_map[int(digits[index])]for char in letters:self.backtracking(digits, index1, schar)def letterCombinations(self, digits: str) - List[str]:if not digits:return []self.backtracking(digits, 0, )return self.res1.6组合总和
39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。
对于给定的输入保证和为 target 的不同组合数少于 150 个。
思路对于前面进行选择的元素我们可以重复地选取对于后面选取的元素我们不能进行重复选取我们需要用一个index参数来控制每次选取的位置这个参数和startIndex还不太一样每次更新的时候我们需要设置indexi。
对于组合问题什么时候需要starIndex来控制for循环的起始位置什么时候不需要呢举个例子如果是一个集合来求组合的话就需要startIndex如果是多个集合来求组合的话各个集合之间互不影响这时就不需要用startIndex了。
class Solution:def __init__(self):self.path: List[int] []self.res: List[List[int]] []def backtracking(self, candidates: List[int], targetSum: int, Sum: int, index: int) - None:if Sum targetSum: # 剪枝return elif Sum targetSum: # 叶子节点并收获结果self.res.append(self.path[:])return for i in range(index, len(candidates)):self.path.append(candidates[i])self.backtracking(candidates, targetSum, Sumcandidates[i], i) # 注意这里index的修改为iself.path.pop()def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:if not candidates:return []self.backtracking(candidates, target, 0, 0)return self.res1.7组合总和II
40. 组合总和 II
给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
思路这道题已经明确表示了会出现重复的元素所以我们需要进行去重操作如何进行去重呢我们先对整个candidates进行排序如果后一个遍历的元素等于前一个遍历的元素那么则跳过当前遍历的过程因为对前一个元素的处理过程相当于已经处理过当前的元素了。
class Solution:def __init__(self):self.res: List[List[int]] []self.path: List[int] []def backtracking(self, candidates: List[int], targetSum: int, Sum: int, startIndex: int) - None:if Sum targetSum: # 剪枝return elif Sum targetSum:self.res.append(self.path[:])return for i in range(startIndex, len(candidates)):if i startIndex and candidates[i] candidates[i-1]: # 要对同一树层使用过的元素进行跳过,进行树层去重跳过当前处理的元素continueself.path.append(candidates[i])self.backtracking(candidates, targetSum, Sumcandidates[i], i1) self.path.pop()def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]:if not candidates:return []candidates.sort() # 首先让当前元素有序self.backtracking(candidates, target, 0, 0)return self.res1.8分割回文串
131. 分割回文串
给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串回文串是向前和向后读都相同的字符串 。返回 s 所有可能的分割方案。
class Solution:def __init__(self):self.path: List[str] []self.res: List[List[str]] []def isPalidrome(self, s: str, start: int, end: int) - bool:判断是否是回文数if start end:return Falsewhile start end:if s[start] s[end]:start 1end - 1else:return Falsereturn Truedef backtracking(self, s: str, startIndex: int) - None:if startIndex len(s):self.res.append(self.path[:])for i in range(startIndex, len(s)):if self.isPalidrome(s, startIndex, i): # 如果是回文串则加入到中间结果中self.path.append(s[startIndex:i1]) # 注意这里的区间是左闭右开self.backtracking(s, i1)self.path.pop()else:continuedef partition(self, s: str) - List[List[str]]:if not s:return []self.backtracking(s, 0)return self.res1.9复原IP地址
93. 复原 IP 地址
有效 IP 地址 正好由四个整数每个整数位于 0 到 255 之间组成且不能含有前导 0整数之间用 . 分隔。
例如0.1.2.201 和 192.168.1.1 是 有效 IP 地址但是 0.011.255.245、192.168.1.312 和 192.1681.1 是 无效 IP 地址。
给定一个只包含数字的字符串 s 用以表示一个 IP 地址返回所有可能的有效 IP 地址这些地址可以通过在 s 中插入 . 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
class Solution:def __init__(self):self.path: List[str] []self.res: List[str] []def isVaild(self, s: str, start: int, end: int) - bool:判断切割是否合法if end - start 1 and s[start] 0:return Falsereturn True if int(s[start:end1]) 255 else Falsedef backtracking(self, s: str, startIndex: int) - None:if len(self.path) 4 and startIndex len(s): # 终止条件self.res.append(..join(self.path))returnfor i in range(startIndex, len(s)):if self.isVaild(s, startIndex, i):self.path.append(s[startIndex:i1])self.backtracking(s, i1)self.path.pop()else:continuedef restoreIpAddresses(self, s: str) - List[str]:if not s:return []self.backtracking(s, 0)return self.res1.10子集问题
78. 子集
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的
子集幂集。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
思路在解决子集问题的时候我们需要时刻进行结果的收获一个问题的就是我们需要收获的结果不全是叶子节点我们只要遇到结果就进行收获所以收获节点会放在终止条件之前。
class Solution:def __init__(self):self.path: List[int] []self.res: List[List[int]] []def backtracking(self, nums: List[int], startIndex: int) - None:self.res.append(self.path[:]) # 只要是节点就满足条件,收获结果在终止条件之前if startIndex len(nums):return for i in range(startIndex, len(nums)):self.path.append(nums[i])self.backtracking(nums, i1)self.path.pop()def subsets(self, nums: List[int]) - List[List[int]]:self.backtracking(nums, 0)return self.res1.11子集II
90. 子集 II
给你一个整数数组 nums 其中可能包含重复元素请你返回该数组所有可能的
子集幂集。解集 不能 包含重复的子集。返回的解集中子集可以按 任意顺序 排列。
思路这道题涉及到去重我们一般有两种去重的思路第一种思路是直接对子集进行排序判断后一个元素是否等于前一个元素如果是则表明已经处理过相同的元素则可以直接跳过第二种思路是用一个set来完成去重set可以用于树层的去重在每一层我都建立一个set如果在当前层中遍历的元素在这个set中则表明已经使用过该元素则跳过反之则继续使用。
解法一回溯排序去重
class Solution:def __init__(self):self.path: List[int] []self.res: List[List[int]] []def backtracking(self, nums: List[int], startIndex: int) - None:self.res.append(self.path[:])if startIndex len(nums):returnfor i in range(startIndex, len(nums)):if i startIndex and nums[i] nums[i-1]: # 进行排序去重continueelse:self.path.append(nums[i])self.backtracking(nums, i1)self.path.pop()def subsetsWithDup(self, nums: List[int]) - List[List[int]]:nums.sort()self.backtracking(nums, 0)return self.res解法二回溯set去重
class Solution:def __init__(self):self.path: List[int] []self.res: List[List[int]] []def backtracking(self, nums: List[int], startIndex: int) - None:self.res.append(self.path[:])if startIndex len(nums):returnuset: set set()for i in range(startIndex, len(nums)):if nums[i] in uset: # 用set进行去重continueelse:uset.add(nums[i])self.path.append(nums[i])self.backtracking(nums, i1)self.path.pop()def subsetsWithDup(self, nums: List[int]) - List[List[int]]:nums.sort() # 用set去重也要排序self.backtracking(nums, 0)return self.res1.12非递减子序列
491. 非递减子序列
给你一个整数数组 nums 找出并返回所有该数组中不同的递增子序列递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。数组中可能含有重复元素如出现两个整数相等也可以视作递增序列的一种特殊情况。
思路我们收集结果的时候也是在终止条件之前唯一的要求就是当前的至少有两个元素并且我们还要对同一树层进行去重这里不能使用排序比较大小去重因为我们不能对这个序列进行排序如果进行排序了那么整个结果的顺序就改变了所以我们只能用set进行去重。
class Solution:def __init__(self):self.path: List[int] []self.res: List[List[int]] []def backtracking(self, nums: List[int], startIndex: int) - None:if len(self.path) 2:self.res.append(self.path[:])if startIndex len(nums):return uset: set set()for i in range(startIndex, len(nums)):if (self.path and nums[i] self.path[-1]) or nums[i] in uset: # 判断是否是非递减序列或者在当前层中当前元素没有被使用continueelse:uset.add(nums[i])self.path.append(nums[i])self.backtracking(nums, i1)self.path.pop()def findSubsequences(self, nums: List[int]) - List[List[int]]:self.backtracking(nums, 0)return self.res1.13全排列
46. 全排列
给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
思路通常的思路是对于每个树的分支我们都维护一个used数组如果其中的对应下表的元素被使用过那么在当前树枝接下来的选取中我们就跳过这个元素并且我们将这个used数组沿着树的深度进行传播同样需要进行回溯为什么在排列问题中不使用startIndex呢因为在组合问题中我们使用startIndex是为了避免后面的元素在同一树层中取之前取过的元素用startIndex来进行限制全排列问题我们不需要进行这一限制所以不需要startIndex总结一句话组合问题需要用startIndex排列问题不需要startIndex。
class Solution:def __init__(self):self.path: List[int] []self.res: List[List[int]] []def backtracking(self, nums: List[int], used: List[bool]) - None:if len(self.path) len(nums):self.res.append(self.path[:])returnfor i in range(len(nums)): # 排列问题不需要使用startIndex来限制树层中取重复元素if used[i] True:continueelse:used[i] Trueself.path.append(nums[i])self.backtracking(nums, used)self.path.pop() # 回溯used[i] False # 回溯def permute(self, nums: List[int]) - List[List[int]]:used: List[bool] [False] * len(nums)self.backtracking(nums, used)return self.res1.14全排列II
给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。
思路利用set进行树层去重利用used进行树枝去重
解法一利用set进行树层去重利用used进行树枝去重
class Solution:def __init__(self):self.path: List[int] []self.res: List[List[int]] []def backtracking(self, nums: List[int], used: List[bool]):if len(self.path) len(nums):self.res.append(self.path[:])return uset: set set() # 利用set进行树层去重利用used进行树枝去重for i in range(len(nums)):if nums[i] in uset or used[i] True:continueelse:uset.add(nums[i]) used[i] Trueself.path.append(nums[i])self.backtracking(nums, used)self.path.pop() # 回溯used[i] False # 回溯def permuteUnique(self, nums: List[int]) - List[List[int]]:used: List[bool] [False] * len(nums)self.backtracking(nums, used)return self.res解法二利用排列进行树层去重利用used进行树枝去重
class Solution:def __init__(self):self.path: List[int] []self.res: List[List[int]] []def backtracking(self, nums: List[int], used: List[bool]):if len(self.path) len(nums):self.res.append(self.path[:])return for i in range(len(nums)): if (i 0 and nums[i] nums[i-1] and used[i-1] False ) or used[i] True: # 利用排列进行树层去重利用used进行树枝去重,这里一定要used[i-1]False才能保证是在树层上进行去重这种解法比较复杂不如解法一continueelse: used[i] Trueself.path.append(nums[i])self.backtracking(nums, used)self.path.pop() # 回溯used[i] False # 回溯def permuteUnique(self, nums: List[int]) - List[List[int]]:used: List[bool] [False] * len(nums)nums.sort()self.backtracking(nums, used)return self.res1.15N皇后
51. N 皇后
按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位。
思路我们需要对棋盘进行二维的一个遍历在回溯算法模板的for循环中即回溯算法的树层中我们来遍历这个棋盘的col在回溯算法的深度中即回溯算法的树深中我们来遍历这个棋盘的row然后通过一个isValid()函数来判断当前的位置是否合法如果合法我们就放置皇后Q如果非法我们就继续搜索最后当我们遍历完所有的row之后我们即可以保存搜索的结果了然后再进行回溯这样我们就能够搜索所有想要的结果。
class Solution:def __init__(self):self.res: List[List[str]] []def isValid(self, chessboard: List[List[str]], row: int, col: int) - bool:# 检查相同列for i in range(row): # 相同col的前n row已经有Q,则非法if chessboard[i][col] Q:return False# 检查相同行for j in range(col):if chessboard[row][j] Q:return False# 检查45°方向i row - 1j col - 1while i 0 and j 0:if chessboard[i][j] Q:return Falsei - 1j - 1# 检查135°方向i row - 1j col 1while i 0 and j len(chessboard):if chessboard[i][j] Q:return Falsei - 1j 1return Truedef backtracking(self, chessboard: List[List[str]], n: int, row: int) - None:if row n: # 遍历完所有行则收集结果self.res.append(chessboard[:])return # 通过树层来遍历colfor col in range(n):if self.isValid(chessboard, row, col):# print(chessboard)chessboard[row] chessboard[row][:col] Q chessboard[row][col1:]self.backtracking(chessboard, n, row1) # 通过树深来遍历rowchessboard[row] chessboard[row][:col] . chessboard[row][col1:] # 回溯def solveNQueens(self, n: int) - List[List[str]]:chessboard: List[List[str]] [.*n]*nself.backtracking(chessboard, n, 0)return self.res1.16解数独
37. 解数独
编写一个程序通过填充空格来解决数独问题。
数独的解法需 遵循如下规则
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图
数独部分空格内已填入了数字空白格用 . 表示。
解法一双重for循环
class Solution:def isValid(self, board: List[List[str]], num: int, row: int, col: int) - bool:# 当前列是否有效for i in range(len(board)):if board[i][col] str(num):return False# 当前行是否有效for j in range(len(board)):if board[row][j] str(num):return False# 当前方格是否有效start_row (row // 3) * 3start_col (col // 3) * 3for i in range(start_row, start_row3):for j in range(start_col, start_col3):if board[i][j] str(num):return Falsereturn Truedef backtracking(self, board: List[List[str]]) - bool:for i in range(len(board)):for j in range(len(board[0])):if board[i][j] ! .:continueelse:for num in range(1,10):if self.isValid(board, num, i, j):board[i][j] str(num)if self.backtracking(board): return Trueboard[i][j] . # 回溯return False # 若数字1-9都不能成功填入空格返回False无解return True # 有解def solveSudoku(self, board: List[List[str]]) - None:Do not return anything, modify board in-place instead.self.backtracking(board)
