代码随想录一刷笔记_回溯算法(上)

60+在408的算法考察难度和深度上还是收手了👍)(上半部分是有关该章节中组合的内容)

回溯算法理论基础

回溯的本质是穷举,找出符合要求的答案。所以回溯算法的效率不会很高。

回溯法解决的问题
  • 组合问题(不强调元素顺序)个数里面按一定规则找出k个数的集合
  • 切割问题:一个字符串按一定规则有几种切割方式
  • 子集问题:一个N个数的集合里有多少符合条件的子集
  • 排列问题(强调元素顺序):N个数按一定规则全排列,有几种排列方式
  • 棋盘问题:N皇后,解数独等
回溯三部曲
  1. 回溯函数返回值以及参数
  2. 回溯函数终止条件
  3. 回溯函数的单层遍历逻辑
递归的三种分类
  1. 直接递归

    函数直接调用自身

  2. 间接递归

    函数通过调用另一个函数,而这个函数又调用了原始函数,形成了递归调用链

    也就是说,递归是在函数之间的相互调用中实现的

  3. 尾递归

    递归调用是函数体中的最后一个操作。

    可以实现尾递归优化操作,以减少堆栈空间的使用,一旦这个调用被返回,当前函数的堆栈帧就可以被释放,实现复用。

组合(77)& 组合总和Ⅲ(216)

整个过程感觉可以认为是在构造二叉树的过程,每一层往结果里push一个新的数,直到满足数量要求后向上返回。

image-20241025234100819
PS. 剪枝

剩余的数组size <数量要求的时候,可以进行剪枝操作。

image-20241025234620246
组合总和Ⅲ

相比上一题,这一题添加了需要满足组合中数总和为某一值的条件,相应可以添加当总和大于这个值时就返回的剪枝条件。

电话号码的字母组合(17)

这一题主要需要解决数字和多个字母间如何映射的问题 -> 使用map或者二维数组定义

使用map声明
1
2
3
4
5
std::map<char, std::string> letterMap = {
{'2', "abc"}, {'3', "def"}, {'4', "ghi"},
{'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"},
{'8', "tuv"}, {'9', "wxyz"}
};
使用二维数组声明
1
2
3
4
5
6
7
8
9
10
11
12
13
const string letterMap[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};

组合总和(38)

这一题的特点是可以在组合里选用重复的数字。

所以在回溯的时候,startindex变量仍然是for循环横向遍历到的值,数组下标通过for循环的横向遍历向前移动。

组合总和Ⅱ(40)

这题不能选用同一个序号的数字,但是不同序号的数字之间是存在重复的情况的,需要考虑如何去重。

假设,在数组为[1, 2, 2, 2],target = 5 的条件下:

a6d55b2be60c404adfaddb62dbea252

显然,此时有多个[1, 2, 2]的结果出现,而且因为元素的个数相同,他们都出现在同一层里面。

所以,可以采取这样的办法:只留下序号靠前的数组,其他的进行舍去。也就是,只使用每一次递归中的第一个startIndex对应的数值,当横向遍历到后面的等于前一个值的情况下,直接舍去。

a7aebdc317aa6eff949ff601fffe791
去重方法(检查当前遍历到的数字之前是否使用过)
  1. 引入vector<bool> used变量对已经遍历过的数组进行判定
  2. 引入set方法查找是否已重复
  3. 在将数压入path前进行判定这个数是否出现过

分割回文串(131)

这一题是要对字符串进行分割,所以回溯的是不同的分割方式(在哪里进行切割)。

按照回溯的三部曲来说:
  1. 回溯的传入参数

    需要传入分割的字符串和处理到字符串的第一个位置startIndex(避免切割线出现重复的情况)

  2. 回溯的结束判断

    与之前寻找组合的判断不同,这里的退出时判断纵深递归的startIndex是否遍历到了最后(如果分割成功,都会遍历到最后一层,如果切割结果不是回文串,将会停止往下遍历)。

  3. 回溯的主体程序部分

    代码的核心环节,如何切割回文串。

    使用for循环对字符串进行切割(使用s.substr(index1, index2)函数),判断前半段字符串是否满足回文串的需求,满足则继续向下递归。

PS. 如何判断回文数

方法1:使用双指针,分别指向头节点和尾节点,向中间遍历;

方法2:使用单指针。

复原IP地址(93)

这一题在分割回文串的基础上提出了进一步的要求:

  1. 将字符串分为四个部分,其中每个部分均处于0-255内
  2. 前三个部分的结尾需要以“.”结尾

子集(78)

这一题主要是考虑递归函数的终止条件:

由于是寻找所有的子集,所以结果树的每一个结果path都应该直接放入result中,而当startIndex遍历到最后一位时,执行return操作。

子集Ⅱ(90)

本题需要去重,去重方法和组合总和Ⅱ相同,需要将同一层树上的重复项删去。

非递减子序列(491)

这一题的测试样例十分逆天,出现了答案错误但是输入输出因为写不下而完全相同的情况。。。。导致我还得去编译器里自己查是什么bug😭。

image-20241106234733174

他是要输出按序的子序列(重复数字也包含),所以与之前的题目不同的是不需要进行预先的排序。按照去重的思路,需要对同一层中出现的重复数字进行去重操作,有三种方法。

但是!因为不需要对序列进行预排序的问题,直接比较当前数字与前一位是行不通的(与他相同的数字可能在前前前面)。

剩下的两种使用布尔型的used向量和使用unordered_set的方法都是可行的。

PS 定义布尔型的向量并初始化为false的办法:

1
vector<bool> used(nums.size(), false);

代码随想录一刷笔记_回溯算法(上)
http://example.com/2024/10/23/code-7-backtracking-1/
作者
Poivre
发布于
2024年10月23日
许可协议