mirror of
https://github.com/youngyangyang04/leetcode-master.git
synced 2026-02-02 18:39:09 +08:00
118 lines
6.5 KiB
Markdown
118 lines
6.5 KiB
Markdown
|
||
|
||
<p align="center">
|
||
<a href="https://mp.weixin.qq.com/s/QVF6upVMSbgvZy8lHZS3CQ"><img src="https://img.shields.io/badge/知识星球-代码随想录-blue" alt=""></a>
|
||
<a href="https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw"><img src="https://img.shields.io/badge/刷题-微信群-green" alt=""></a>
|
||
<a href="https://img-blog.csdnimg.cn/20201210231711160.png"><img src="https://img.shields.io/badge/公众号-代码随想录-brightgreen" alt=""></a>
|
||
<a href="https://space.bilibili.com/525438321"><img src="https://img.shields.io/badge/B站-代码随想录-orange" alt=""></a>
|
||
</p>
|
||
|
||
--------------------------
|
||
|
||
# 本周小结！（回溯算法系列一）
|
||
|
||
## 周一
|
||
|
||
本周我们正式开始了回溯算法系列，那么首先当然是概述。
|
||
|
||
在[关于回溯算法，你该了解这些！](https://programmercarl.com/回溯算法理论基础.html)中介绍了什么是回溯，回溯法的效率，回溯法解决的问题以及回溯法模板。
|
||
|
||
**回溯是递归的副产品，只要有递归就会有回溯**。
|
||
|
||
回溯法就是暴力搜索，并不是什么高效的算法，最多在剪枝一下。
|
||
|
||
回溯算法能解决如下问题：
|
||
|
||
* 组合问题：N个数里面按一定规则找出k个数的集合
|
||
* 排列问题：N个数按一定规则全排列，有几种排列方式
|
||
* 切割问题：一个字符串按一定规则有几种切割方式
|
||
* 子集问题：一个N个数的集合里有多少符合条件的子集
|
||
* 棋盘问题：N皇后，解数独等等
|
||
|
||
是不是感觉回溯算法有点厉害了。
|
||
|
||
回溯法确实不好理解，所以需要把回溯法抽象为一个图形来理解就容易多了，每一道回溯法的题目都可以抽象为树形结构。
|
||
|
||
针对很多同学都写不好回溯，我在[关于回溯算法，你该了解这些！](https://programmercarl.com/回溯算法理论基础.html)用回溯三部曲，分析了回溯算法，并给出了回溯法的模板。
|
||
|
||
这个模板会伴随整个回溯法系列！
|
||
|
||
## 周二
|
||
|
||
|
||
在[回溯算法：求组合问题！](https://programmercarl.com/0077.组合.html)中，我们开始用回溯法解决第一道题目，组合问题。
|
||
|
||
我在文中开始的时候给大家列举k层for循环例子，进而得出都是同样是暴力解法，为什么要用回溯法。
|
||
|
||
**此时大家应该深有体会回溯法的魅力，用递归控制for循环嵌套的数量！**
|
||
|
||
本题我把回溯问题抽象为树形结构，可以直观的看出其搜索的过程：**for循环横向遍历，递归纵向遍历，回溯不断调整结果集**。
|
||
|
||
## 周三
|
||
|
||
针对[回溯算法：求组合问题！](https://programmercarl.com/0077.组合.html)还可以做剪枝的操作。
|
||
|
||
在[回溯算法：组合问题再剪剪枝](https://programmercarl.com/0077.组合优化.html)中把回溯法代码做了剪枝优化，在文中我依然把问题抽象为一个树形结构，大家可以一目了然剪的究竟是哪里。
|
||
|
||
**剪枝精髓是：for循环在寻找起点的时候要有一个范围，如果这个起点到集合终止之间的元素已经不够 题目要求的k个元素了，就没有必要搜索了**。
|
||
|
||
## 周四
|
||
|
||
在[回溯算法：求组合总和！](https://programmercarl.com/0216.组合总和III.html)中，相当于 [回溯算法：求组合问题！](https://programmercarl.com/0077.组合.html)加了一个元素总和的限制。
|
||
|
||
整体思路还是一样的，本题的剪枝会好想一些，即：**已选元素总和如果已经大于n（题中要求的和）了，那么往后遍历就没有意义了，直接剪掉**。
|
||
|
||
在本题中，依然还可以有一个剪枝，就是[回溯算法：组合问题再剪剪枝](https://programmercarl.com/0077.组合优化.html)中提到的，对for循环选择的起始范围的剪枝。
|
||
|
||
所以，剪枝的代码，可以把for循环，加上 `i <= 9 - (k - path.size()) + 1` 的限制！
|
||
|
||
组合总和问题还有一些花样，下周还会介绍到。
|
||
|
||
## 周五
|
||
|
||
在[回溯算法：电话号码的字母组合](https://programmercarl.com/0017.电话号码的字母组合.html)中，开始用多个集合来求组合，还是熟悉的模板题目，但是有一些细节。
|
||
|
||
例如这里for循环，可不像是在 [回溯算法：求组合问题！](https://programmercarl.com/0077.组合.html)和[回溯算法：求组合总和！](https://programmercarl.com/0216.组合总和III.html)中从startIndex开始遍历的。
|
||
|
||
**因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而[回溯算法：求组合问题！](https://programmercarl.com/0077.组合.html)和[回溯算法：求组合总和！](https://programmercarl.com/0216.组合总和III.html)都是是求同一个集合中的组合！**
|
||
|
||
如果大家在现场面试的时候，一定要注意各种输入异常的情况，例如本题输入1 * #按键。
|
||
|
||
其实本题不算难，但也处处是细节，还是要反复琢磨。
|
||
|
||
## 周六
|
||
|
||
因为之前链表系列没有写总结，虽然链表系列已经是两个月前的事情，但还是有必要补一下。
|
||
|
||
所以给出[链表：总结篇！](https://programmercarl.com/链表总结篇.html)，这里对之前链表理论基础和经典题目进行了总结。
|
||
|
||
同时对[链表：环找到了，那入口呢？](https://programmercarl.com/0142.环形链表II.html)中求环入口的问题又进行了补充证明，可以说把环形链表的方方面面都讲的很通透了，大家如果没有做过环形链表的题目一定要去做一做。
|
||
|
||
## 总结
|
||
|
||
相信通过这一周对回溯法的学习，大家已经掌握其题本套路了，也不会对回溯法那么畏惧了。
|
||
|
||
回溯法抽象为树形结构后，其遍历过程就是：**for循环横向遍历，递归纵向遍历，回溯不断调整结果集**。
|
||
|
||
这个是我做了很多回溯的题目，不断摸索其规律才总结出来的。
|
||
|
||
对于回溯法的整体框架，网上搜的文章这块一般都说不清楚，按照天上掉下来的代码对着讲解，不知道究竟是怎么来的，也不知道为什么要这么写。
|
||
|
||
所以，录友们刚开始学回溯法，起跑姿势就很标准了。
|
||
|
||
下周依然是回溯法，难度又要上升一个台阶了。
|
||
|
||
最后祝录友们周末愉快！
|
||
|
||
**如果感觉「代码随想录」不错，就分享给身边的同学朋友吧，一起来学习算法！**
|
||
|
||
|
||
|
||
------------------------
|
||
|
||
* 微信：[程序员Carl](https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw)
|
||
* B站：[代码随想录](https://space.bilibili.com/525438321)
|
||
* 知识星球：[代码随想录](https://mp.weixin.qq.com/s/QVF6upVMSbgvZy8lHZS3CQ)
|
||
|
||
<div align="center"><img src='https://file1.kamacoder.com/i/algo/01二维码.jpg' width=450> </img></div>
|