LeetCode算法训练-回溯总结
2023-03-31 10:36:22 时间
欢迎关注个人公众号:爱喝可可牛奶
LeetCode算法训练-回溯总结
适用问题
- 组合问题:N个数里面按一定规则找出k个数的集合
- 排列问题:N个数按一定规则全排列,有几种排列方式
- 切割问题:一个字符串按一定规则有几种切割方式
- 子集问题:一个N个数的集合里有多少符合条件的子集
- 棋盘问题:N皇后,解数独等等
通用模板
result 存放结果集
path 某个符合条件的结果
void backtracking(参数) {
if (终止条件) {
result.add(path);
return;
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
}
个人理解
-
回溯和递归紧密相联,有递归就有回溯
-
回溯的过程可以抽象为一个回溯树,要搞清楚题目要求的是分支节点、叶子节点、还是所有节点
-
去重 回溯树的同一个树枝去重(用全局used数组) 同一个树层上去重(for循环外的局部used数组)
-
画回溯树找条件写代码,什么时候要添加结果,什么时候要continue,要不要以及能不能对原始数据集排序
-
剪枝优化 什么情况下不用再递归树枝不用递归树层,这时可直接在for循环中给出限制条件
-
回溯函数遍历树枝,for循环++遍历树层
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十