附近网站建设,哪里可以发广告,wordpress淘宝客单页模板,全球十大软件公司排名Part I : 回溯算法基础
对回溯算法不清楚的可以参看前一篇#xff1a;代码随想录算法训练营第24天| 第七章 回溯算法part01 理论基础、leetcode 77
Part II: 相关题目
Leetcode 216.组合总和III
解决问题#xff1a;在数字1~9之间#xff0c;找出k个数且它们的和为n从而…Part I : 回溯算法基础
对回溯算法不清楚的可以参看前一篇代码随想录算法训练营第24天| 第七章 回溯算法part01 理论基础、leetcode 77
Part II: 相关题目
Leetcode 216.组合总和III
解决问题在数字1~9之间找出k个数且它们的和为n从而确定组合如n3, k2,则组合为[[1,2]] 组合问题是取出一组比如封神选六个帅哥当质子团排列问题是按顺序排成一列比如质子团按武力值排名每个月都要打一次架决定最强的算法描述利用回溯算法去确定组合使得算法复杂度为O(n)(n-k1)!百度组合、排列的计算公式即可知这里的n是指问题规模哈千万别望文生义算法难点其实和77没啥大差别就是增加了回溯函数的参数组合的回溯算法模板也熟悉的差不多了看来写博客虽累但效果还是有的。代码
# 未剪枝版
class Solution:def combinationSum3(self, k: int, n: int) - List[List[int]]:path[] # 用于接收单层递归-回溯结果res[] # 用于接收总递归-回溯结果# 这里的start1代表从数字1开始# tempsum0代表单层递归-回溯过程得到的和self.backtracking(k,n,path,res,1,0)return resdef backtracking(self,k,targetsum,path,res,start,tempsum):# 终止条件与77题相比增加了内层判断只有当tempsumtempsum即目标和才加入到res并返回if (len(path))k:if targetsumtempsum:res.append(path[:])return# 单层处理# 横向遍历只使用数字1到9for i in range(start,10):tempsumipath.append(i)self.backtracking(k,targetsum,path,res,i1,tempsum)tempsum-ipath.pop()图示过程即还原为树形结构与77类似 剪枝代码示例
class Solution:def combinationSum3(self, k: int, n: int) - List[List[int]]:path[]res[]self.backtracking(k,n,path,res,1,0)return resdef backtracking(self,k,targetsum,path,res,start,tempsum):# 剪枝时必须增加该终止条件若不加则报错具体原因看上面的图示if tempsumtargetsum:return# 终止条件if (len(path))k:if targetsumtempsum:res.append(path[:])return# 单层处理# 横向遍历只使用数字1到9# 剪枝:9-(k-len(path))29-(k-len(path))11,后面的1是因为ragne函数左取右舍的特性for i in range(start,9-(k-len(path))2):tempsumipath.append(i)self.backtracking(k,targetsum,path,res,i1,tempsum)tempsum-ipath.pop()Leetcode 17.电话号码的字母组合 解决问题给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合这里给出的数字-字母映射表与键盘拇指输入法一致比如输入digits “23” 输出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”] 算法描述利用回溯算法去确定组合使得算法复杂度为O(n)(n-k1)!百度组合、排列的计算公式即可知这里的n是指问题规模哈千万别望文生义 算法难点对我来说是加上了数字-字母映射表后的变化啦。 代码
class Solution:def letterCombinations(self, digits: str) - List[str]:# 数字-字母映射表letter_map {0:,1:,2:abc,3:def,4:ghi,5:jkl,6:mno,7:pqrs,8:tuv,9:wxyz}# 存储单层递归-回溯结果s# 存储总递归-回溯结果res[]# 进行回溯index10代表从digits[0]开始遍历self.backtracking(digits,0,s,res,letter_map)return resdef backtracking(self,digits,index1,s,res,letter_map):# 根据测试用例要加上这个终止条件否则返回[]而非[]if len(digits)0:return# 设置终止条件如果遍历完了digits则返回if index1len(digits):res.append(s[:])return# 从letter_map映射表中找到对应的字母集合digit_index int(digits[index1])letters letter_map[digit_index]# 处理遍历-递归-回溯过程for i in range(len(letters)):# PS:这里s是字符串赋值方式要改变哈ssletters[i]self.backtracking(digits,index11,s,res,letter_map)ss[:-1]今日打卡总结
有了昨天的基础今天的博客轻松些了~ 之前差的day2~day23的博客也要慢慢补上来 fighting!
