石家庄哪里有网站建设,轻食网络推广方案,广州网站建设集团,广东网站seo策划算法总结2 回溯与深广搜算法一、理解回溯算法1.1、回溯的概念1.2、回溯法的效率1.3、回溯法问题分类1.4、回溯法的做题步骤二、经典问题2.1、组合问题2.1.1、77. 组合 - 值不重复2.1.2、216.组合总和III - 值不重复且等于目标值2.1.3、17. 电话号码的字母组合 - 双层回溯2.1.4、…
算法总结2 回溯与深广搜算法一、理解回溯算法1.1、回溯的概念1.2、回溯法的效率1.3、回溯法问题分类1.4、回溯法的做题步骤二、经典问题2.1、组合问题2.1.1、77. 组合 - 值不重复2.1.2、216.组合总和III - 值不重复且等于目标值2.1.3、17. 电话号码的字母组合 - 双层回溯2.1.4、39. 组合总和 - 可复选同一值2.1.5、40.组合总和II - 不可复选同一值,但有重复元素2.1.6、练习22. 括号生成2.2、分割问题2.2.1、131. 分割回文串 - 回溯附加条件2.2.2、93.复原IP地址 - 回溯附加条件2.3、子集问题2.3.1、78. 子集 - 整棵遍历数2.3.2、90. 子集 II - 乱序重复元素去重复值2.4、排列问题2.4.1、46.全排列2.4.2、47.全排列 II2.5、应用型类似问题2.5.1、491.递增子序列 和子集问题很像- 非排序重复元素去重2.5.2、332.重新安排行程和2.1.3、17. 电话号码的字母组合 很像2.6、棋盘问题2.6.1、HJ43 迷宫问题2.6.2、51. N 皇后2.6.3、37. 解数独三、深搜DFS与广搜BFS3.1、岛屿问题200. 岛屿数量1. 深度优先搜索DFS2. 广度优先搜索 BFS1254. 统计封闭岛屿的数目1.深度优先搜索DFS2.广度优先搜索3.深度优先/广度优先 去除边界连通面积1020.飞地的数量695. 岛屿的最大面积1.深度优先搜索DFS2.广度优先搜索 BFS1905. 统计子岛屿130. 被围绕的区域417. 太平洋大西洋水流问题3.2、集合划分问题(等用于回溯的问题)698. 划分为k个相等的子集473. 火柴拼正方形2305. 公平分发饼干1723. 完成所有工作的最短时间3.3、其他问题547. 省份数量参考一、理解回溯算法
回溯与深广搜有相似的做法和理解所以把他们放在同一个文章之中文章看似篇幅很长实际上题目都是相似的顺着章节来可以很快的掌握这个算法内容以后碰到这样的相似题目会很快想出思路。
1.1、回溯的概念
回溯是递归的纵横拓展主要是递归纵局部暴力枚举横。所以可以从递归和暴力两个方面来拆解回溯问题。 由上图可知回溯法的所有问题都可以抽象为树形结构集合的大小构成了树的宽度递归深度构成了树的深度N叉树。因为递归有终止条件所以树的高度会有限同时递归的最终结果会呈现在叶子节点上。 1.2、回溯法的效率
从上一节的概念可知回溯递归暴力搜索所以它并不是一个特别高效的算法即便再做一些剪枝优化下依旧改变不了它的整体就是穷举的特性。
但即便这个算法效率不高它的使用依旧很广泛因为很多问题除了穷举实在就是没有别的解决办法了具体可以看看下一章的例题感受下。 1.3、回溯法问题分类
回溯法主要解决以下五种问题
问题描述组合问题N个数里面按一定规则找出k个数的集合切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集排列问题N个数按一定规则全排列有几种排列方式棋盘问题N皇后解数独迷宫等等1.4、回溯法的做题步骤
回溯法三部曲
回溯函数的模板返回值以及参数 这里回溯函数起名为backtracking回溯算法中函数返回值一般为空。 对于参数的话很难提前确定下来一般是先写逻辑然后需要什么参数就填什么参数。
def backtracking(参数):回溯函数终止条件 什么时候达到了终止条件树中就可以看出一般来说搜到叶子节点了也就找到了满足条件的一条答案把这个答案存放起来并结束本层递归。
if 终止条件:保存结果return回溯搜索的遍历过程
# 横向遍历。一个节点有多少个孩子就执行多少次
for i in [本层集合中的元素树中及节点孩子的数量就是集合的大小]:处理节点# 纵向遍历自己调用自己实现递归backtracking(路径选择列表)回溯撤销处理结果总结
def backtracking(参数):if 终止条件:存放结果returnfor i in [本层集合中的元素树中及节点孩子的数量就是集合的大小]:处理节点# 纵向遍历自己调用自己实现递归backtracking(路径选择列表)回溯撤销处理结果二、经典问题 2.1、组合问题 2.1.1、77. 组合 - 值不重复
力扣题目链接
1.使用函数 itertools库下的combinations组合函数与之对应的是permutations排列函数。
from itertools import combinations
class Solution:def combine(self, n: int, k: int) - List[List[int]]:l [i1 for i in range(n)]res combinations(l, k)return list(res)2.回溯法 从题目可以知道k2两层循环解决k3三层循环但是题目的k是变动的也就是for循环的层数是需要是变动的那么回溯法就用递归来解决层数嵌套每递归一次就是一层for循环一个简单的过程如下 n相当于树的宽度k相当于树深度的
class Solution:def combine(self, n: int, k: int) - List[List[int]]:# 存放符合条件结果的集合result []# 存放符合条件单一结果path []# startIndex来记录下一层递归搜索的起始位置def backtracking(n, k, startIndex):if len(path)k:# 这里注意要添加一个path的拷贝直接append为原址# path最后会被pop结果为空值result.append(path[:])returnfor i in range(startIndex, n1):path.append(i)backtracking(n, k, i1)path.pop()backtracking(n, k, 1)return result
加上剪枝操作(当path为固定长度时) 如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了那么就没有必要搜索了。那么后面这些部分可以剪掉如下只用更改循环的终止条件改变范围就行。
# 这里
# n - (k-len(path))1恰好满足最后一个长度到结尾
# 再往右就不满足了
# n 4, k 2, 当len(path) 1 时
# 4 - (2 - 1) 1 4从startindex到4都是可以取的
endIndex n - (k-len(path))1
for i in range(startIndex, endIndex1):path.append(i)backtracking(n, k, i1)path.pop()当然这个剪枝是针对有固定长度k才可取。
综上为
class Solution:def combine(self, n: int, k: int) - List[List[int]]:# 存放符合条件结果的集合result []# 存放符合条件单一结果path []# startIndex来记录下一层递归搜索的起始位置def backtracking(n, k, startIndex):if len(path)k:result.append(path[:])return# n 4, k 2, 当len(path) 1 时# 4 - (2 - 1) 1 4从startindex到4都是可以取的endIndex n - (k-len(path))1for i in range(startIndex, endIndex1):path.append(i)backtracking(n, k, i1)path.pop()backtracking(n, k, 1)return result 2.1.2、216.组合总和III - 值不重复且等于目标值
力扣题目链接
1.使用函数
from itertools import combinations
class Solution:def combinationSum3(self, k: int, n: int) - List[List[int]]:res []l combinations([i1 for i in range(9)], k)for i in list(l):if sum(i)n:res.append(i)return res2.回溯搜索
class Solution:def combinationSum3(self, k: int, n: int) - List[List[int]]:res []path []def backtracking(ind):if len(path)k:if sum(path)n:res.append(path[:])return# 剪枝1同前面的原理endindex 9-(k-len(path))1for i in range(ind, endindex1):path.append(i)# 剪枝2和大了就不继续回溯这个放前面backtracking下第一行也行if sum(path)n:backtracking(i1)path.pop()backtracking(1)return res加上两次剪枝
class Solution:def combinationSum3(self, k: int, n: int) - List[List[int]]:path []res []def backtracking(k, n, startIndex):# 剪枝1大于目标值再遍历也没意义直接去掉if sum(path)n:returnif len(path)k and sum(path)n:res.append(path[:])return# 剪枝2需要搭配剪枝1否则k-len(path)会为负数循环次数反而会增加endIndex 9 - (k-len(path))1for i in range(startIndex, endIndex1):path.append(i)backtracking(k, n, i1)path.pop()backtracking(k, n, 1)return res本题与77.组合 加了元素总和的限制同样的把问题抽象为树形结构按照回溯算法的步骤走最后给出剪枝的优化。 2.1.3、17. 电话号码的字母组合 - 双层回溯
力扣题目链接
回溯法1从digits的角度
class Solution:def letterCombinations(self, digits: str) - List[str]:d {2:abc, 3:def, 4:ghi, 5:jkl, 6:mno, 7:pqrs,8:tuv,9:wxyz}# 存储根节点path []# 存储最终结果res []# 回溯数字def backtracking(digits):if len(digits)0:# 去除空值非空则添加字符串if path:res.append(.join(path[:]))return# 循环取一个数字对应的字母for i in d[digits[0]]:# 存一个该数字的字母path.append(i)# 去除第一个数字后面的数字串backtracking(digits[1:])path.pop()backtracking(digits)return res回溯法2从index的角度
class Solution:def letterCombinations(self, digits: str) - List[str]:alphas {2:abc,3:def,4:ghi,5:jkl,6:mno,7:pqrs,8:tuv,9:wxyz}path []res []def backtracking(ind):if len(path)len(digits):if path:res.append(.join(path[:]))returnfor a in alphas[digits[ind]]:path.append(a)backtracking(ind1)path.pop()backtracking(0)return res注意输入1 * #按键等等异常情况。代码中最好考虑这些异常情况但题目的测试数据中应该没有异常情况的数据但是要知道会有这些异常如果是现场面试中就一定要考虑到。 2.1.4、39. 组合总和 - 可复选同一值
力扣题目链接
回溯法1,candidates角度
class Solution:def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:path []res []def backtracking(candidates):# 大于目标值直接返回空if sum(path)target:if sum(path)target and sorted(path) not in res:# 值存进去之前提前排序便于去重res.append(sorted(path[:]))return# 循环整个列表注意这里会产生重复结果只是顺序不同for i in candidates:path.append(i)backtracking(candidates)path.pop()backtracking(candidates)return res回溯法2,index角度 这里加上循环的起始索引并引入一个su_m变量去存储每一步的sum。
class Solution:def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:path []res []def backtracking(candidates, su_m, startIndex):# 因为循环进行了优化所以这里判断会简单许多if su_mtarget:if su_mtarget:res.append(path[:])return# [2,3,5,7], 7# 这种循环索引而不是列表值会优先考虑重复# 所以不会出现[2,3,2]和[3,2,2]这种重复的排列# 优先[2,2,2,2]得不到target开始popfor i in range(startIndex, len(candidates)):su_m candidates[i]path.append(candidates[i])# 这里起始索引为i因为可以重复使用backtracking(candidates, su_m, i)# 回溯要减去值su_m - candidates[i]path.pop()backtracking(candidates, 0, 0)return res这里还可以简化下
class Solution:def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:res []path []def backtracking(ind):if sum(path)target:res.append(path[:])returnfor i in range(ind, len(candidates)):path.append(candidates[i])if sum(path)target:backtracking(i)path.pop()# 这里直接一个index即可backtracking(0)return res回溯1会产生排列,要去重而回溯2只产生组合。 剪枝优化 当判断sum target后就没有必要进入下一层递归。
对总集合排序之后如果下一层的sum就是本层的 sum candidates[i]已经大于target就可以结束本轮for循环的遍历。
class Solution:def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:path []res []def backtracking(candidates, su_m, startIndex):if su_mtarget:res.append(path[:])returnfor i in range(startIndex, len(candidates)):# 排序后小的值的和都大于target后续大的无序继续# 不排序结果会出问题if su_m candidates[i] target:returnsu_m candidates[i]path.append(candidates[i])backtracking(candidates, su_m, i)su_m - candidates[i]path.pop()# 注意要排序candidates.sort()backtracking(candidates, 0, 0)return res2.1.5、40.组合总和II - 不可复选同一值,但有重复元素
力扣题目链接 本题的难点在于集合数组candidates有重复元素但还不能有重复的组合。
回溯法1超时 把所有组合求出来去除重复的。
class Solution:def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]:path []res []def backtracking(candidates, su_m, startIndex):# 这里会有重复的如[1,1,2,5,6,7,10],8# 第一个1与第二个1意义不同[1,2,5] 和 [1,2,6], [1,7]和[1,7]# 但对结果来说相同。if su_m target and path[:] not in res:res.append(path[:])return for i in range(startIndex, len(candidates)):if su_m candidates[i]target:returnsu_m candidates[i]path.append(candidates[i])backtracking(candidates, su_m, i1) su_m - candidates[i]path.pop()candidates.sort()backtracking(candidates, 0, 0)return res这里会有重复的如[1,1,2,5,6,7,10],8。
第一个1与第二个1意义不同[1,2,5] 和 [1,2,6], [1,7]和[1,7]但对结果来说相同。
所以只需要第一次的1就可以同一树层第一次出现的重复元素会遍历到后面的重复元素记一次就行树层的其他相同的直接去掉。
把所有组合求出来再去重这么做很容易超时所以要在搜索的过程中就去掉重复组合。
回溯法2使用startIndex去重 既然求结果去重会超时那么就需要在求的过程中提前去重。
这里直接使用startIndex进行判断去重同一个树层(for循环内)和上一个元素相等则continue跳过。
class Solution:def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]:path []res []def backtracking(startIndex):# 这里会有重复的如[1,1,2,5,6,7,10]# 第一个1与第二个1意义不同但对结果来说相同if sum(path) target:res.append(path[:])return for i in range(startIndex, len(candidates)):# 只是用索引来判断重复。这里注意不是i0# 因为每一层的元素有更新得从startIndex开始# 否则i0则不存在重复元素了if istartIndex and candidates[i] candidates[i-1]:continuesu_m candidates[i]path.append(candidates[i])if sum(path)target:backtracking(i1) su_m - candidates[i]path.pop()candidates.sort()backtracking(0)return res回溯法3新建used数组去重 used[i - 1] true说明同一树枝candidates[i - 1]使用过纵向 used[i - 1] false说明同一树层candidates[i - 1]使用过横向
class Solution:def combinationSum2(self, candidates: List[int], target: int) - List[List[int]]:path []res []used [False] * len(candidates)def backtracking(startIndex):# 这里会有重复的如[1,1,2,5,6,7,10]# 第一个1与第二个1意义不同但对结果来说相同if sum(path) target:res.append(path[:])return for i in range(startIndex, len(candidates)):# 上个相同节点没使用过为False可以判断为同一树层则跳过# 上个相同节点使用过为True可以判断为同一树枝不跳# 这里注意不同于前面istartIndex# 本来i0不允许任何重复但used[i-1]False表示同一层从这个相同点开始前面一个相同点已经回溯成False了if i0 and candidates[i] candidates[i-1] and used[i-1]False:continueused[i]Truepath.append(candidates[i])if sum(path)target:backtracking(i1) # 回溯为了下一轮for loop used[i]Falsesu_m - candidates[i]path.pop()candidates.sort()backtracking(0)return res2.1.6、练习
22. 括号生成
22. 括号生成
class Solution:def generateParenthesis(self, n: int) - List[str]:res []path []def backtracking(l, r):if ln and rn:res.append(.join(path))if ln:path.append(()backtracking(l1,r)path.pop()if rl:path.append())backtracking(l,r1)path.pop()backtracking(0,0)return res2.2、分割问题
2.2.1、131. 分割回文串 - 回溯附加条件
力扣题目链接
回溯双指针
class Solution:def partition(self, s: str) - List[List[str]]:res []path []# 判断回文的函数# 正反序
# def isPalindrome(s, start, end):
# if s[start:end1] s[start:end1][::-1]:
# return True
# return False# 双指针def isPalindrome(s, start, end):while startend:if s[start] ! s[end]:return Falsestart1end-1return Truedef backtracking(s, startIndex):if startIndex len(s):res.append(path[:])returnfor i in range(startIndex, len(s)):# 判断是否为回文是再添加到path# 不是回文则切割失败后续操作跳过if isPalindrome(s, startIndex, i):path.append(s[startIndex:i1])else:continuebacktracking(s, i1)path.pop()backtracking(s, 0)return res回溯正反序:
class Solution:def partition(self, s: str) - List[List[str]]:res []path []def backtracking(ind):if indlen(s):res.append(path[:])for i in range(ind, len(s)):if s[ind:i1]!s[ind:i1][::-1]:continuepath.append(s[ind:i1])backtracking(i1)path.pop()backtracking(0)return res2.2.2、93.复原IP地址 - 回溯附加条件
力扣题目链接
回溯法1, 使用index 思路同上一题切割成4份为终止标准结合startIndex判断是否遍历完整字符串将合法的结果用’.拼接即可。
class Solution:def restoreIpAddresses(self, s: str) - List[str]:res []path []# 判断是否合法# 1. 0-255 之间闭区间# 2. 当长度大于1时(或不为0)首位不能为0def isValid(s, start, end):if 0int(s[start:end1])255 and \(s[start:end1]0 or s[start:end1].lstrip(0)s[start:end1]):# 首位不能为0则去除首位的0后还是原来的字符串则首位无0return Truereturn Falsedef backtracking(startIndex):# 终止条件为截取了4段if len(path)4:# 截取4段并且索引到了尾部即取了所有字符if startIndex len(s):# 将结果用.拼接起来res.append(..join(path[:]))return # 遍历字符串for i in range(startIndex, len(s)):if isValid(s, startIndex, i) and len(path)4:path.append(s[startIndex:i1])backtracking(i1)path.pop()backtracking(0)return res回溯法2使用string
class Solution:def restoreIpAddresses(self, s: str) - List[str]:res[]path[]def isvalid(string):if len(string)len(str(int(string))) and 0int(string)255:return Truereturn Falsedef dfs(s):if len(path)4 and s:return Falseif len(path)4 and not s:res.append(..join(path[:]))returnfor i in range(len(s)):if isvalid(s[:i1]):path.append(s[:i1])dfs(s[i1:])path.pop()dfs(s)return res2.3、子集问题
2.3.1、78. 子集 - 整棵遍历数
力扣题目链接 注幂集就是集合的所有子集。
回溯法
class Solution:def subsets(self, nums: List[int]) - List[List[int]]:res []path []def backtracking(nums, startIndex):# 子集就是遍历整个树res.append(path[:])if startIndex len(nums):returnfor i in range(startIndex, len(nums)):path.append(nums[i])backtracking(nums, i1)path.pop()backtracking(nums, 0)return res从上图可知求取子集问题不需要任何剪枝因为子集就是要遍历整棵树。 2.3.2、90. 子集 II - 乱序重复元素去重复值
力扣题目链接 思路同 40. 数组总和 II即去重去掉同一树层的重复节点。
回溯法
class Solution:def subsetsWithDup(self, nums: List[int]) - List[List[int]]:res []path []def backtracking(startIndex):res.append(path[:])if startIndex len(nums):returnfor i in range(startIndex, len(nums)):# 同一树层相似的则先去掉if istartIndex and nums[i]nums[i-1]:continuepath.append(nums[i])backtracking(i1)path.pop()# 需要排序便于把相似的排到一起nums.sort()backtracking(0)return res注意 一定要对元素进行排序这样我们才方便通过相邻的节点来判断是否重复使用了。
子集题做完建议试试 2.6.1、491.递增子序列
class Solution:def subsetsWithDup(self, nums: List[int]) - List[List[int]]:res []path []def backtracking(ind):res.append(path[:])if indlen(nums):return# 每一层标记重复used set()for i in range(ind, len(nums)):# 有重复的跳过前面已经遍历过if nums[i] in used:continue# 按层添加used.add(nums[i])path.append(nums[i])backtracking(i1)path.pop()# nums.sort()backtracking(0)return res2.4、排列问题
排列是有序的也就是说 [1,2] 和 [2,1] 是两个集合这和之前分析的子集以及组合所不同的地方。
2.4.1、46.全排列
力扣题目链接
回溯法1数组截断传递
class Solution:def permute(self, nums: List[int]) - List[List[int]]:res []path []def backtracking(nums):# 每次传入的nums是变动的逐渐变为空所以不能len(path)len(nums)if not nums:res.append(path[:])return# 从索引0开始因为每次都要取到所有数for i in range(len(nums)):path.append(nums[i])# 去掉被选中的nums[i]选取其他段拼在一起backtracking(nums[:i]nums[i1:])path.pop()backtracking(nums)return res回溯法2used数组
class Solution:def permute(self, nums: List[int]) - List[List[int]]:res []path []# 创建一个flag数组保存结果是否使用过used_list [False]*len(nums)def backtracking(nums, used_list):# 每次传入的nums是固定的则len(path)len(nums)if len(path) len(nums):res.append(path[:])returnfor i in range(len(nums)):# 已经使用过则去重if used_list[i]True:continueused_list[i] Truepath.append(nums[i])backtracking(nums, used_list)used_list[i] Falsepath.pop()backtracking(nums, used_list)return res回溯法3去掉used 最简单的写法因为无重复元素所以path可以代替used_list。
class Solution:def permute(self, nums: List[int]) - List[List[int]]:res []path []def backtracking(nums):# 每次传入的nums是固定的则len(path)len(nums)if len(path) len(nums):res.append(path[:])returnfor i in range(len(nums)):# 因为本题为无重复元素所以path内的元素是唯一的if nums[i] in path:continuepath.append(nums[i])backtracking(nums)path.pop()backtracking(nums)return res可以看出元素1在[1,2]中已经使用过了但是在[2,1]中还要在使用一次1所以处理排列问题就不用使用startIndex了。
排列问题的不同
每层都是从0开始搜索而不是startIndex 需要used数组记录path里都放了哪些元素了 2.4.2、47.全排列 II
力扣题目链接
这里必须使用used_list布尔列表一个是原来的作用即判断使用使用过另一个是判断在同一层和此元素相同的值之前是否使用过。使用过直接跳过否则是相同的操作结果。
class Solution:def permuteUnique(self, nums: List[int]) - List[List[int]]:res []path []used_list [False]*len(nums)def backtracking(nums, used_list):if len(nums) len(path):res.append(path[:])returnfor i in range(len(nums)):# 每次递归都是所有元素# 1.该元素自身被使用过continueif used_list[i] True:continue# 2.该元素同一层有之前有重复则只算一次则这一次continue# used_list[i-1]True表示同一层之前使用过# 同一层去重效率高即取False效率比True高if (i0 and nums[i]nums[i-1]) and used_list[i-1]False:continueused_list[i] Truepath.append(nums[i])backtracking(nums, used_list)used_list[i] Falsepath.pop()nums.sort()backtracking(nums, used_list)return res2.5、应用型类似问题
2.5.1、491.递增子序列 和子集问题很像- 非排序重复元素去重
力扣题目链接
本题求自增子序列是不能对原数组经行排序的排完序的数组都是自增子序列了所以不能使用之前的去重逻辑
回溯法集合去重 #深度遍历中每一层都会有一个全新的usage_list用于记录本层元素是否重复使用
class Solution:def findSubsequences(self, nums: List[int]) - List[List[int]]:res []path []def backtracking(startIndex):if len(path)2:res.append(path[:])if startIndexlen(nums):return# 这里要放在内部因为每一层子树都要去重# 用来记录非重复的元素用来去重判断used_list set()# 单层递归逻辑# 深度遍历中每一层都会有一个全新的usage_list用于记录本层元素是否重复使用for i in range(startIndex, len(nums)):# 这个去重只能判断排序后相邻的数组# 所以像[4,7,6,7]在这里不可用#if istartIndex and if nums[i] nums[i-1]:# continue# path非空且后一个小于前一个即小于path的最后一个元素 # 或者 同一树层后面重复出现不同于前面的相邻重复出现if (path and nums[i]path[-1]) or nums[i] in used_list:continueused_list.add(nums[i])path.append(nums[i])backtracking(i1)path.pop()backtracking(0)return res回溯法哈希表去重
class Solution:def findSubsequences(self, nums: List[int]) - List[List[int]]:res []path []def backtracking(nums, startIndex):if len(path)2:res.append(path[:])if startIndexlen(nums):return# 使用哈希表去重也就是数组或列表used_list [False] * 201 # 使用列表去重题中取值范围[-100, 100]for i in range(startIndex, len(nums)):if (path and nums[i]path[-1]) or used_list[nums[i]100]True:continue# 100将-100 - 100变为0 - 200used_list[nums[i]100] Truepath.append(nums[i])backtracking(nums, i1)path.pop()backtracking(nums, 0)return res在图中可以看出同一父节点下的同层上使用过的元素就不能在使用了。与前面的同一层相邻重复的不同。 2.5.2、332.重新安排行程和2.1.3、17. 电话号码的字母组合 很像
力扣题目链接
这一题可参考 2.1.3、17. 电话号码的字母组合 - 双层回溯自己创建映射进行遍历回溯只不过电话号码里面是寻找所有组合每个数字对于字母的选择是所有而且能重复选择而行程里面每个地点对应的地点列表里有效的只有部分并且在选择了某地点后下一次的地点列表需要将其去除。如何将其去除这是一个难点。
回溯法1普通解法超时
class Solution:def findItinerary(self, tickets: List[List[str]]) - List[str]:res []path []used_list [False]*len(tickets)def backtracking(tickets):if len(path) len(tickets):res.append(path[:])return# 每次遍历整个list前面的通用解法但对于这一题这样会超时for i in range(len(tickets)):if used_list[i] True:continueif i0 and tickets[i] tickets[i-1] and used_list[i-1]True:continueif (path and (path[-1][-1]tickets[i][0])) or (not path and tickets[i][0] JFK):used_list[i] Truepath.append(tickets[i])backtracking(tickets)used_list[i] Falsepath.pop()backtracking(tickets)# 将结果按字典排序final sorted(res)[0]r []# 所有list只取第一个值加上最后一个list取最后一个值for i in range(len(final)):r.append(final[i][0])if i len(final)-1:r.append(final[i][1])return r回溯法2 重新设置tickets为一个新的对象进行简化处理这样就无需遍历整个tickets。
class Solution:def findItinerary(self, tickets: List[List[str]]) - List[str]:res []path [JFK]# 创建一个空字典值为空listticket_dict defaultdict(list)for item in tickets:ticket_dict[item[0]].append(item[1])# 排序1 提前排序 或者在内部排序for t in ticket_dict:ticket_dict[t].sort()tickets_dict里面的内容是这样的{JFK: [SFO, ATL], SFO: [ATL], ATL: [JFK, SFO]})# 根据字典的key去延伸到value再对应到下一个key......以此类推def backtracking(start_point):if len(path) len(tickets)1:return True# 内部排序咱们使用外面的排序方法只用遍历一次# ticket_dict[start_point].sort()for _ in ticket_dict[start_point]:# 取出一个值选择一个落地点end_point ticket_dict[start_point].pop(0)path.append(end_point)# 只要找到一个就可以直接返回了这里设置成bool# 并且path直接为正确结果跳过path.pop()还原if backtracking(end_point):return Truepath.pop()ticket_dict[start_point].append(end_point)backtracking(JFK)return path做回溯相关问题时先思考以下几点 排列或组合有无序是否有重复元素有什么不同需要什么或不需要什么
总结如下
回溯问题组合排列幂集回溯函数参数使用startIndex每进一层(startIndex, len(nums))即找startIndex后面的元素进行组合防止重复值。任意参数。有重复组合值只是排列不同startIndex无意义使用used布尔列表为True则表示访问过去掉。同组合额外变量只需startIndex即可 / used布尔list / 同一层的used集合used布尔list同组合遍历顺序从startInde开始搜索(startIndex, len(nums))从头开始搜索(len(nums)同组合有重复元素无序/有序无序则先进行排序下面三种不同方法排除重复组合直接continue [1] istartIndex and nums[i]nums[i-1] [2] i0 and nums[i]nums[i-1] and nums[i-1]False [3] 同一层 usedset() nums[i] in usedused只有append无pop。无序则先进行排序除了自身是否使用过进行判断其余判断同前面组合对同一层是否重复使用进行判断。同组合无重复元素无序/有序无需排序常规回溯写法无需排序常规回溯写法used判断/path代替used同组合结果同长度组合同长度排列不同长度节点上所有元素。当数组无重复元素幂集的结果大小为2数组长度2^{数组长度}2数组长度。
注意 这是常规解法对本文章以及很多特定其他解法没有包含进去等算法达到了一定的水平可以自行创造。 2.6、棋盘问题 2.6.1、HJ43 迷宫问题
华为机试牛客网链接 回溯法
# 字符串转数字和迷宫
h, w map(int, input().split())
maze []
for i in range(h):maze.append(list(map(int, input().split())))# 初始化
# 起点
result [(0, 0)]
# 走过的路径进行标记防止回溯死循环
maze[0][0] 3# 判断该点是否合法
# 1.范围2.路或墙
def isVaild(x, y):if 0 x h and 0 y w and maze[x][y] 0:return Truereturn False# 回溯
def backtracking(x, y):# 打印每一步的坐标点# print(x,y)# 终止条件到达右下角终点if x h - 1 and y w - 1:# result.append((x, y))return result回溯前从第一个方向开始第一个条件先判断下一步是否合法合法再进行深度优先搜索1.同时对走过的路径进行标记为32.将坐标加入到result结果中搜索成功1和2成立搜索失败进行回溯1. 将走过的路径进行回溯但不能改为原值0可改为2另一个值或者不改也可以2. 将result进行回溯pop退出结果选择下一个方向如果四个方向都失败则返回False说明该方向的深度优先无法走到终点# 下if isVaild(x 1, y):result.append((x 1, y))maze[x 1][y] 3if backtracking(x 1, y):return True# 回溯result.pop()maze[x 1][y] 2# 上if isVaild(x - 1, y):result.append((x - 1, y))maze[x - 1][y] 3if backtracking(x - 1, y):return True# 回溯result.pop()maze[x - 1][y] 2# 左if isVaild(x, y - 1):result.append((x, y - 1))maze[x][y - 1] 3if backtracking(x, y - 1):return True# 回溯result.pop()maze[x][y - 1] 2# 右if isVaild(x, y 1):result.append((x, y 1))maze[x][y 1] 3if backtracking(x, y 1):return True# 回溯result.pop()maze[x][y 1] 2# 上下左右都不行则返回Falsereturn False
backtracking(0, 0)
print(result)
print(maze)测试输入
h,w map(int, 5 5.split())
maze []
deal [0 1 0 0 0, 0 1 1 1 0, 0 0 0 0 0,0 1 1 1 0,0 0 0 1 0]
for i in deal:maze.append(list(map(int, i.split())))[[0, 1, 0, 0, 0],[0, 1, 1, 1, 0],[0, 0, 0, 0, 0],[0, 1, 1, 1, 0],[0, 0, 0, 1, 0]]结果
0 0
1 0
2 0
3 0
4 0
4 1
4 2
2 1
2 2
2 3
2 4
3 4
4 4
[(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4)]
[[3, 1, 0, 0, 0],[3, 1, 1, 1, 0],[3, 3, 3, 3, 3],[2, 1, 1, 1, 3],[2, 2, 2, 1, 3]]2.6.2、51. N 皇后
力扣题目链接
回溯法
class Solution:def solveNQueens(self, n: int) - List[List[str]]:res []board [[.]*n for _ in range(n)]# 判断是否合法def isVaild(board, row, col):# 1. 判断同一列是否冲突for i in range(row1):if board[i][col] Q:return False# 2.判断左上是否冲突tmp_row rowtmp_col colwhile 0tmp_rown and 0tmp_coln:if board[tmp_row][tmp_col] Q:return Falsetmp_row-1tmp_col-1# 3.判断右上是否冲突tmp_row rowtmp_col colwhile 0tmp_rown and 0tmp_coln:if board[tmp_row][tmp_col] Q:return Falsetmp_row-1tmp_col1return True# 每一行进行遍历def backtracking(row, board):if row n:tmp []for i in board:tmp.append(.join(i))res.append(tmp)return# 每一行的每一列进行选取for col in range(n):if not isVaild(board, row, col):continueboard[row][col] Q# 进入下一行backtracking(row1, board)board[row][col] .backtracking(0, board)return res皇后们的约束条件
不能同行不能同列不能同斜线
符合条件则继续下一行否则同行的下一列。
这题是hard题其实难度并不大当做 2.1.3、17. 电话号码的字母组合 和 332.重新安排行程 来做每一行为索引进行遍历内部每一列进行遍历回溯。
难点在于判断条件即约束条件上是否有Q。我们一般拆成4个部分横竖正斜反斜但实际上横无需判断因为每一行的行为树根这个只会按顺序递增而由此引出子树列才需要回溯只会产生一个Q。并且斜左下与斜右下也无需遍历因为一定为空一定没有Q因为还没遍历到那个位置所以咱们的判断以该点为水平线的上面部分为区间即可这样可以降低复杂度。 2.6.3、37. 解数独
力扣题目链接
回溯法
class Solution:def solveSudoku(self, board: List[List[str]]) - None:Do not return anything, modify board in-place instead.def isVaild(row, col, val, board):# 判断同一行是否冲突for i in range(9):if board[row][i] str(val):return False# 判断同一列是否冲突for i in range(9):if board[i][col] str(val):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(val):return Falsereturn True# 若有解返回True无解返回Falsedef backtracking(board):# 这里遍历完即是终止条件# 遍历整个表行和列for i in range(len(board)):for j in range(len(board[0])):# 若空格内已经有数字则跳过if board[i][j] ! .:continue# 逐渐填入1-10for k in range(1, 10):# 有效则继续递归if isVaild(i, j, k, board):board[i][j] str(k)if backtracking(board):return True# 回溯board[i][j] .# 若数字1-9都不能成功填入空格返回False无解return False# 有解说明已经填满了到了最后一步所有的board[i][j] ! .return Truebacktracking(board)N皇后问题是因为每一行每一列只放一个皇后只需要一层for循环遍历一行递归来来遍历列然后一行一列确定皇后的唯一位置。
本题就不一样了本题中棋盘的每一个位置都要放一个数字并检查数字是否合法解数独的树形结构要比N皇后更宽更深。
这里需要的是一个二维的递归也就是两个for循环嵌套着递归这个二维的递归与下一章中的深搜与广搜有很深的联系如果你能理解其一对这题或者下一章的题目的理解都非常的简单。
一个for循环遍历棋盘的行一个for循环遍历棋盘的列一行一列确定下来之后递归遍历这个位置放9个数字的可能性。如果一行一列确定下来了这里尝试了9个数都不行说明这个棋盘找不到解决数独问题的解。
判断棋盘是否合法有如下三个维度
同行是否重复同列是否重复9宫格里是否重复
同时一定要注意最后的两层循环之外需要return True因为棋盘都填满了这是满足结果的需要传回布尔True给if backtracking()去判断从而继续return True防止后续的回溯而还原结果导致即便搜到了结果因为回溯还原了最后board还是原来的空的。
同时题目要求只有一个结果时我们把backtracking当做布尔if去判断通过return True防止回溯。 当题目要求有多个结果时我们就当普通的backtracking为一行回溯前将结果通过path存到res中。 三、深搜DFS与广搜BFS
深广搜问题相比回溯问题少了退回的操作但思路大致相似所以该类型题目会更加容易。
3.1、岛屿问题
基本上能用dfs做的题目也能用bfs来做所以可以尝试用这两种方法去解题。这样对该类型算法的理解会更加深刻。 200. 岛屿数量
200. 岛屿数量 非常常规和经典的DFS和BFS题目。 1. 深度优先搜索DFS
dfs题目的模板与回溯法类似但是没有退回操作因为都是有效操作。
class Solution:def numIslands(self, grid: List[List[str]]) - int:# 避免重复将结果存进来或者grid[i][j]0遍历过变成湖泊避免死循环grid_set set()res 0def dfs(i, j):for x, y in (i1, j), (i-1, j), (i, j1), (i, j-1):if 0xlen(grid) and 0ylen(grid[0]) and grid[x][y]1 and (x,y) not in grid_set:# 遍历过的结果存到grid_setgrid_set.add((x,y))# 将符合条件的(x,y)继续迭代dfs(x,y)for i in range(len(grid)):for j in range(len(grid[0])):# 为陆地并且没被遍历过if grid[i][j]1 and (i,j) not in grid_set:res1grid_set.add((i,j))dfs(i,j)return res因为整个地图给到我们我们不用将结果存起来去判断重复直接遍历过的变成 0 湖泊就行了那么少一个grid_set的空间以及搜索时间效率会提高:
class Solution:def numIslands(self, grid: List[List[str]]) - int:res 0def dfs(i, j):grid[i][j]0 # 这里改成非1的任何值都可以for x, y in (i1, j), (i-1, j), (i, j1), (i, j-1):if 0xlen(grid) and 0ylen(grid[0]) and grid[x][y]1:# 将符合条件的(x,y)继续迭代dfs(x,y)for i in range(len(grid)):for j in range(len(grid[0])):# 为陆地并且没被遍历过if grid[i][j]1:res1dfs(i,j)return res2. 广度优先搜索 BFS
from collections import deque
class Solution:def numIslands(self, grid: List[List[str]]) - int:res 0for i in range(len(grid)):for j in range(len(grid[0])):# 为陆地并且没被遍历过if grid[i][j]1:res1grid[i][j]0# 用队列代替列表存储加快速度neighbors deque([(i,j)])# 从一个点开始向周围扩散广度优先扩散到完成退出找下一个点while neighbors:# 从左起点开始取所有点# 为什么从左开始先搜索完该点的第一外层# 随后第二外层等等依次继续xi, yj neighbors.popleft()# 后面的代码同dfs但是内部没有嵌套dfs也就不会无限的深度找而是找一次即外层一圈即可。for x, y in (xi1, yj), (xi-1, yj), (xi, yj1), (xi, yj-1):if 0xlen(grid) and 0ylen(grid[0]) and grid[x][y]1:neighbors.append((x, y))grid[x][y]0return res1254. 统计封闭岛屿的数目
1254. 统计封闭岛屿的数目 求封闭的个数那么分为非封闭与封闭岛屿需要在搜索的过程中对不符合条件的进行标记被标记上的岛屿总数不会1。
1.深度优先搜索DFS
遍历所有面积去除与边界连通的面积即边界位置有1岛屿的。
class Solution:def closedIsland(self, grid: List[List[int]]) - int:row len(grid)col len(grid[0])res 0def dfs(i, j):# 同样遍历过的点进行标注防止死循环或重复遍历grid[i][j]1for x, y in (i1, j), (i-1, j), (i, j1), (i, j-1):if 0xrow and 0ycol and grid[x][y]0:# 有不符合条件的点该面积标注为0即不合理if x0 or xrow-1 or y0 or ycol-1:nonlocal flagflag0dfs(x, y)for i in range(1, row-1):for j in range(1, col-1):flag 1if grid[i][j]0:dfs(i, j)# 符合条件无边界为0或row、col长度的面积则合理if flag:res1return res2.广度优先搜索
from collections import deque
class Solution:def closedIsland(self, grid: List[List[int]]) - int:row len(grid)col len(grid[0])res 0for i in range(1, row-1):for j in range(1, col-1):flag 1if grid[i][j]0:grid[i][j]1# 同样使用队列代替列表加速neighbors deque([(i, j)])while neighbors:xi, yj neighbors.popleft()for x, y in (xi1, yj),(xi-1, yj),(xi,yj1),(xi,yj-1):if 0xrow and 0ycol and grid[x][y]0:# 判断条件不符合条件的标记为0if x0 or xrow-1 or y0 or ycol-1:flag 0# 添加下一圈点以及避免重复进行相反值标记neighbors.append((x,y))grid[x][y]1# 符合条件无边界为0或row、col长度的面积则合理if flag:res1return res3.深度优先/广度优先 去除边界连通面积
class Solution:def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) - int:row len(grid1)col len(grid1[0])res 0# 常规dfsdef dfs(i,j):grid2[i][j]0for x, y in (i1,j),(i-1,j),(i,j1),(i,j-1):if 0xrow and 0ycol and grid2[x][y]1:dfs(x ,y)# 求B在A中的子集B有A没有的点延伸的面积全部变成0for i in range(row):for j in range(col):if grid1[i][j]0 and grid2[i][j]1:dfs(i,j)# 最后剩下的grid2中的1的岛屿即A的子集for i in range(row):for j in range(col):if grid2[i][j]1:res1dfs(i,j)return res1020.飞地的数量
1020.飞地的数量
这题同上思路不过不是统计面积无需再dfs而是统计为1的格子数量那么直接遍历即可。
class Solution:def numEnclaves(self, grid: List[List[int]]) - int:row len(grid)col len(grid[0])res 0# 同上def dfs(i,j):grid[i][j]0for x, y in (i1,j),(i-1,j),(i,j1),(i,j-1):if 0xrow and 0ycol and grid[x][y]1:dfs(x,y)for i in range(row):if grid[i][0]1:dfs(i,0)if grid[i][col-1]1:dfs(i,col-1)for j in range(col):if grid[0][j]1:dfs(0,j)if grid[row-1][j]1:dfs(row-1,j)# 统计图上都是1的格子数量for i in range(1, row-1):for j in range(1, col-1):if grid[i][j]1:res1return res广度优先的写法也很简单同上。 695. 岛屿的最大面积
695. 岛屿的最大面积 同前面将所有面积计算出来每次max最大的即可。
1.深度优先搜索DFS
class Solution:def maxAreaOfIsland(self, grid: List[List[int]]) - int:row len(grid)col len(grid[0])# 保存最大的结果max_area 0def dfs(i,j):grid[i][j]0# 这里是关键每遍历一个点面积1nonlocal areaarea1for x, y in (i1, j),(i-1,j),(i,j1),(i,j-1):if 0xrow and 0ycol and grid[x][y]1:dfs(x,y)for i in range(row):for j in range(col):if grid[i][j]1:area 0dfs(i,j)# 取最大的面积max_area max(max_area, area)return max_area2.广度优先搜索 BFS
from collections import deque
class Solution:def maxAreaOfIsland(self, grid: List[List[int]]) - int:row len(grid)col len(grid[0])max_area 0for i in range(row):for j in range(col):if grid[i][j]1:area 0grid[i][j]0neighbors deque([(i,j)])while neighbors:xi, yj neighbors.popleft()# 面积1area1for x, y in (xi1, yj), (xi-1, yj), (xi, yj1),(xi,yj-1):if 0xrow and 0ycol and grid[x][y]1:neighbors.append((x,y))grid[x][y]0max_area max(area, max_area)return max_area1905. 统计子岛屿
1905. 统计子岛屿
class Solution:def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) - int:row len(grid1)col len(grid1[0])res 0def dfs(i,j):grid2[i][j]0for x, y in (i1,j),(i-1,j),(i,j1),(i,j-1):if 0xrow and 0ycol and grid2[x][y]1:dfs(x ,y)# 求B在A中的子集B有A没有的点延伸的面积全部变成0for i in range(row):for j in range(col):if grid1[i][j]0 and grid2[i][j]1:dfs(i,j)# 最后剩下的grid2中的1的岛屿即A的子集for i in range(row):for j in range(col):if grid2[i][j]1:res1dfs(i,j)return res广度优先的写法也很简单同上。 130. 被围绕的区域
130. 被围绕的区域
class Solution:def solve(self, board: List[List[str]]) - None:row len(board)col len(board[0])def dfs(i,j):board[i][j]Zfor x, y in (i1, j),(i-1, j),(i, j1),(i,j-1):if 0xrow and 0ycol and board[x][y]O:dfs(x,y)# 两竖边界for i in range(row):if board[i][0]O:dfs(i,0)if board[i][col-1]O:dfs(i,col-1)# 两横边界for j in range(col):if board[0][j]O:dfs(0,j)if board[row-1][j]O:dfs(row-1,j)for i in range(row):for j in range(col):if board[i][j]O:board[i][j]Xif board[i][j]Z:board[i][j]O广度优先的写法也很简单同上。 417. 太平洋大西洋水流问题
417. 太平洋大西洋水流问题
这题也是需要判断区域的四个边界以此为判断能否流出两种河流的结果。 除此之外该题的图内的值不可更改所以需要另外创建visited去存储访问过的点visited可以为图大小的二维数组也可以为set集合或者list列表。
class Solution:def pacificAtlantic(self, heights: List[List[int]]) - List[List[int]]:row len(heights)col len(heights[0])res []def dfs(i,j):visited.add((i,j))if i0 or j0:nonlocal sign_pacificsign_pacific 1if irow-1 or jcol-1:nonlocal sign_atlanticsign_atlantic 1if sign_pacific and sign_atlantic:return Truefor x,y in (i1, j),(i-1,j),(i,j1),(i,j-1):if 0xrow and 0ycol:if heights[x][y]heights[i][j] and (x,y) not in visited:dfs(x, y)for i in range(row):for j in range(col):sign_pacific 0sign_atlantic 0# 不能改变原图的值所以避免重复值则需要新创建一个图visited set()dfs(i,j)if sign_pacific and sign_atlantic:res.append([i,j])return res3.2、集合划分问题(等用于回溯的问题)
698. 划分为k个相等的子集
698. 划分为k个相等的子集 要划分相等子集首先要判断能否划分即能否被k整除能的话再继续下一步判断。
k个子集相当于k个桶将nums的物品依次丢入到这k个桶中去每一个可能放可能不放复杂度为O(kn)O(k^n)O(kn)相当于暴力搜索。
按序深搜每个物品放入每个桶中能放入该桶则深搜下一个物品不能则回溯放入下一个桶中。如果每个桶都不能放则退出了k个桶的循环return False。
class Solution:def canPartitionKSubsets(self, nums: List[int], k: int) - bool:target sum(nums)if target%k:return Falsetarget //k# 优化1将nums物品按照从大道小排序可减少搜搜复杂度。# 如果物品大小大于背包4个桶装不下可以直接False# 等于背包则直接放入而装满进行下一个nums.sort(reverseTrue)bucket [0]*kdef dfs(ind):if indlen(nums):return Truefor i in range(k):# 优化2如果桶的大小相同当放一个物品放不下时放另一个相等大小的桶也一样放不下则直接跳过不一样大小的桶进行dfsif i0 and bucket[i]bucket[i-1]:continue# 优化3这里没更改if bucket[i]nums[ind]target:再继续后面的# 把 if bucket[i]target and dfs(ind1): 拆开bucket[i]nums[ind]if bucket[i]target and dfs(ind1):return Truebucket[i]-nums[ind]return Falsereturn dfs(0)473. 火柴拼正方形
473. 火柴拼正方形
class Solution:def makesquare(self, matchsticks: List[int]) - bool:target sum(matchsticks)if target%4:return Falsetarget //4bucket [0]*4matchsticks.sort(reverseTrue)def backtracking(ind):if indlen(matchsticks):return Truefor i in range(4):if i0 and bucket[i]bucket[i-1]:continuebucket[i]matchsticks[ind]if bucket[i]target and backtracking(ind1):return Truebucket[i]-matchsticks[ind]return Falsereturn backtracking(0) 2305. 公平分发饼干
2305. 公平分发饼干 以cookies [8,15,10,20,8]和k2为例
相当于吧所有的方法找出来 [61, 0] [53, 8] [41, 20] [33, 28] [51, 10] [43, 18] [31, 30] [23, 38] [46, 15] [38, 23] [26, 35] [18, 43] [36, 25] [28, 33] [16, 45] [8, 53] 去找bucket里的最大值整体的最小值 res min(res, max(bucket)) 因为复杂度很高再进行剪枝
import math
class Solution:def distributeCookies(self, cookies: List[int], k: int) - int:# 因为可能无法均分所以这里不去设置target值而是设置一个变动的res# res逐渐变小但是是bucket里的最大值# target sum(cookies)# target math.ceil(target/k)# 从最大值开始找最小值因为小就接近于均分 res float(inf)# 优化1cookies.sort(reverseTrue)bucket [0]*kdef backtracking(ind):if indlen(cookies):# print(bucket)nonlocal resres min(res, max(bucket))returnfor i in range(k):# 优化2if i0 and bucket[i]bucket[i-1]:continue# 优化3 剪枝有桶大于res直接去掉if bucket[i]cookies[ind]res:bucket[i]cookies[ind]backtracking(ind1)bucket[i]-cookies[ind]backtracking(0)return res 1723. 完成所有工作的最短时间
1723. 完成所有工作的最短时间
class Solution:def minimumTimeRequired(self, jobs: List[int], k: int) - int:res float(inf)bucket [0]*kjobs.sort(reverseTrue)def backtracking(ind):if indlen(jobs):nonlocal resres min(res, max(bucket))return Truefor i in range(k):if i0 and bucket[i]bucket[i-1]:continueif bucket[i]jobs[ind]res:bucket[i]jobs[ind]backtracking(ind1)bucket[i]-jobs[ind]return Falsebacktracking(0)return res 3.3、其他问题
547. 省份数量
547. 省份数量 这题是以一个表来展现相邻这与岛的相邻不同不能直接判表中的1相邻实际上咱们每一行站在列的角度行的列不相交则不会直接相邻可能间接相邻需要深度搜索若相交则一定相邻。当然这只是个思考判断方法具体做题是另一种思路。
这里行与列一定相等把坐标表示为城市名字。 遍历每一行即从第一个城市开始探索与其相邻的城市第一行是与0节点相连的所有其他城市值为1则对其显示的列坐标城市转到对应的行再进行深度搜索寻找与其相邻的城市重复该步骤并且用visited进行存储已经存在则无需重复再搜。
class Solution:def findCircleNum(self, isConnected: List[List[int]]) - int:row len(isConnected)col len(isConnected[0])res 0def dfs(i):visited.add(i)for j in range(row):if j not in visited and isConnected[i][j]1:dfs(j)visited set()for i in range(row):if i not in visited:dfs(i)res1print(visited)return res 深广搜问题相比回溯问题更加的简单并且都有相似且固定的模板相信你通过这篇文章能对回溯与深广搜有了较为深刻的学习和认识
参考
Fairly Nerdy carlprogramming
