代码随想录一刷笔记_回溯算法(上)
60+在408的算法考察难度和深度上还是收手了👍)(上半部分是有关该章节中组合的内容)
回溯算法理论基础
回溯的本质是穷举,找出符合要求的答案。所以回溯算法的效率不会很高。
回溯法解决的问题
- 组合问题(不强调元素顺序)个数里面按一定规则找出k个数的集合
- 切割问题:一个字符串按一定规则有几种切割方式
- 子集问题:一个N个数的集合里有多少符合条件的子集
- 排列问题(强调元素顺序):N个数按一定规则全排列,有几种排列方式
- 棋盘问题:N皇后,解数独等
回溯三部曲
- 回溯函数返回值以及参数
- 回溯函数终止条件
- 回溯函数的单层遍历逻辑
递归的三种分类
直接递归
函数直接调用自身
间接递归
函数通过调用另一个函数,而这个函数又调用了原始函数,形成了递归调用链
也就是说,递归是在函数之间的相互调用中实现的
尾递归
递归调用是函数体中的最后一个操作。
可以实现
尾递归优化
操作,以减少堆栈空间的使用,一旦这个调用被返回,当前函数的堆栈帧就可以被释放,实现复用。
组合(77)& 组合总和Ⅲ(216)
整个过程感觉可以认为是在构造二叉树的过程,每一层往结果里push一个新的数,直到满足数量要求后向上返回。
PS. 剪枝
当剩余的数组size
<数量要求
的时候,可以进行剪枝操作。
组合总和Ⅲ
相比上一题,这一题添加了需要满足组合中数总和为某一值的条件,相应可以添加当总和大于这个值
时就返回的剪枝条件。
电话号码的字母组合(17)
这一题主要需要解决数字和多个字母间如何映射的问题 -> 使用map或者二维数组定义
使用map声明
1 |
|
使用二维数组声明
1 |
|
组合总和(38)
这一题的特点是可以在组合里选用重复的数字。
所以在回溯的时候,startindex变量仍然是for循环横向遍历到的值,数组下标通过for循环的横向遍历向前移动。
组合总和Ⅱ(40)
这题不能选用同一个序号的数字,但是不同序号的数字之间是存在重复的情况的,需要考虑如何去重。
假设,在数组为[1, 2, 2, 2],target = 5 的条件下:
显然,此时有多个[1, 2, 2]的结果出现,而且因为元素的个数相同,他们都出现在同一层里面。
所以,可以采取这样的办法:只留下序号靠前的数组,其他的进行舍去。也就是,只使用每一次递归中的第一个startIndex对应的数值,当横向遍历到后面的等于前一个值的情况下,直接舍去。
去重方法(检查当前遍历到的数字之前是否使用过)
- 引入
vector<bool> used
变量对已经遍历过的数组进行判定 - 引入
set
方法查找是否已重复 - 在将数压入
path
前进行判定这个数是否出现过
分割回文串(131)
这一题是要对字符串进行分割,所以回溯的是不同的分割方式(在哪里进行切割)。
按照回溯的三部曲来说:
回溯的传入参数
需要传入分割的字符串和处理到字符串的第一个位置startIndex(避免切割线出现重复的情况)
回溯的结束判断
与之前寻找组合的判断不同,这里的退出时判断纵深递归的startIndex是否遍历到了最后(如果分割成功,都会遍历到最后一层,如果切割结果不是回文串,将会停止往下遍历)。
回溯的主体程序部分
代码的核心环节,如何切割回文串。
使用for循环对字符串进行切割(使用s.substr(index1, index2)函数),判断前半段字符串是否满足回文串的需求,满足则继续向下递归。
PS. 如何判断回文数
方法1:使用双指针,分别指向头节点和尾节点,向中间遍历;
方法2:使用单指针。
复原IP地址(93)
这一题在分割回文串的基础上提出了进一步的要求:
- 将字符串分为四个部分,其中每个部分均处于0-255内
- 前三个部分的结尾需要以“.”结尾
子集(78)
这一题主要是考虑递归函数的终止条件:
由于是寻找所有的子集,所以结果树的每一个结果path都应该直接放入result中,而当startIndex遍历到最后一位时,执行return操作。
子集Ⅱ(90)
本题需要去重,去重方法和组合总和Ⅱ
相同,需要将同一层树上的重复项删去。
非递减子序列(491)
这一题的测试样例十分逆天,出现了答案错误但是输入输出因为写不下而完全相同的情况。。。。导致我还得去编译器里自己查是什么bug😭。
他是要输出按序的子序列(重复数字也包含),所以与之前的题目不同的是不需要进行预先的排序。按照去重的思路,需要对同一层中出现的重复数字进行去重操作,有三种方法。
但是!因为不需要对序列进行预排序的问题,直接比较当前数字与前一位是行不通的(与他相同的数字可能在前前前面)。
剩下的两种使用布尔型的used向量和使用unordered_set的方法都是可行的。
PS 定义布尔型的向量并初始化为false的办法:
1 |
|