打卡第22天------回溯算法

时间:2024-10-09 07:19:30

开始学习了,希望我可以尽快成功上岸!

一、回溯理论基础
  • 什么是回溯法?

回溯法也可以叫做回溯搜索法,它是一种搜索的方式。

回溯是递归的副产品,只要有递归就会有回溯。

  • 回溯法的效率

回溯法的本质是穷举,穷举所有可能,然后找出我们想要的答案。如果想让回溯法高效一些,可以加一些剪枝的操作,但也改不了回溯法就是穷举的本质。

组合无序,排列有序。

  • 回溯法模板

回溯三部曲,可以按照如下步骤:

  1. 回溯函数模板返回值以及参数

  2. 回溯函数终止条件

  3. 回溯搜索的遍历过程 

回溯函数遍历过程伪代码如下:

  1. for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
  2. 处理节点;
  3. backtracking(路径,选择列表); // 递归
  4. 回溯,撤销处理结果
  5. }

for循环就是遍历集合区间,可以理解一个节点有多少个孩子,这个for循环就执行多少次。

backtracking这里自己调用自己,实现递归。

大家可以从图中看出for循环可以理解是横向遍历,backtracking(递归)就是纵向遍历,这样就把这棵树全遍历完了,一般来说,搜索叶子节点就是找的其中一个结果了。

分析完过程,回溯算法模板框架如下:

  1. void backtracking(参数) {
  2. if (终止条件) {
  3. 存放结果;
  4. return;
  5. }
  6. for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
  7. 处理节点;
  8. backtracking(路径,选择列表); // 递归
  9. 回溯,撤销处理结果
  10. }
  11. }
  • 总结

回溯和递归是相辅相成的。

回溯法其实就是暴力查找,并不是什么高效的算法。

二、组合

题目链接:77. 组合

题目描述:

给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。

来看一下Js代码,是按照卡尔的官方视频讲解写出来的,提交leetcode是可以通过的:

  1. /**
  2. * @param {number} n
  3. * @param {number} k
  4. * @return {number[][]}
  5. */
  6. var combine = function (n, k) {
  7. // 回溯法
  8. let result = [],
  9. path = [];
  10. let backtracking = (_n, _k, startIndex) => {
  11. // 终止条件
  12. if (path.length === _k) {
  13. result.push(path.slice());
  14. return;
  15. }
  16. // 循环本层集合元素
  17. for (let i = startIndex; i <= _n; i++) {
  18. path.push(i);
  19. // 递归
  20. backtracking(_n, _k, i + 1);
  21. // 回溯操作
  22. path.pop();
  23. }
  24. };
  25. backtracking(n, k, 1);
  26. return result;
  27. };
'
运行

剪枝操作:

  1. /**
  2. * @param {number} n
  3. * @param {number} k
  4. * @return {number[][]}
  5. */
  6. var combine = function(n, k) {
  7. const res = [], path = [];
  8. backtracking(n, k, 1);
  9. return res;
  10. function backtracking (n, k, i){
  11. const len = path.length;
  12. if(len === k) {
  13. res.push(Array.from(path));
  14. return;
  15. }
  16. for(let a = i; a <= n + len - k + 1; a++) {
  17. path.push(a);
  18. backtracking(n, k, a + 1);
  19. path.pop();
  20. }
  21. }
  22. };
'
运行
三、电话号码的字母组合

题目链接:17. 电话号码的字母组合

题目描述:

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

看一下具体的JS代码吧

  1. /**
  2. * @param {string} digits
  3. * @return {string[]}
  4. */
  5. var letterCombinations = function(digits) {
  6. const twoArr = [
  7. "", // 0
  8. "", // 1
  9. "abc", // 2
  10. "def", // 3
  11. "ghi", // 4
  12. "jkl", // 5
  13. "mno", // 6
  14. "pqrs", // 7
  15. "tuv", // 8
  16. "wxyz", // 9
  17. ]
  18. let s = []
  19. let result = [];
  20. const backtraking = (digits, index) => {
  21. if (index == digits?.length) {
  22. const str = s.join('')
  23. if (!str) {
  24. return result;
  25. }
  26. result.push(str)
  27. return;
  28. };
  29. const digit = Number(digits.charAt(index))
  30. const stringLetter = twoArr[digit];
  31. for (let i =0;i <stringLetter.length;i++) {
  32. console.log(stringLetter.charAt(i))
  33. s.push(stringLetter.charAt(i))
  34. backtraking(digits, index + 1);
  35. s.pop();
  36. }
  37. }
  38. backtraking(digits, 0)
  39. return result;
  40. };
'
运行
四、组合总和III

题目链接:216. 组合总和 III

题目描述:

找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:

  • 只使用数字1到9
  • 每个数字 最多使用一次 

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。

来看一下按照卡尔的官方视频讲解写出来的JS代码吧:

  1. /**
  2. * @param {number} k
  3. * @param {number} n
  4. * @return {number[][]}
  5. */
  6. var combinationSum3 = function(k, n) {
  7. let path = [], result = [];
  8. const backtracking = (targetSum, k, sum, startIndex) => {
  9. // 剪枝操作
  10. if (sum > targetSum) {
  11. return;
  12. }
  13. // 终止条件
  14. if (path?.length === k) {
  15. if (targetSum == sum) {
  16. result.push(path.slice());
  17. }
  18. return
  19. }
  20. // 剪枝操作,至多指向那个nMax就可以了,再向后就没有意义了。
  21. const nMax = 9 - (k - path.length) + 1;
  22. for(let i = startIndex; i<= nMax;i++) {
  23. sum += i;
  24. path.push(i);
  25. backtracking(targetSum, k, sum, i + 1);
  26. sum -= i;
  27. path.pop();
  28. }
  29. };
  30. backtracking(n, k, 0, 1)
  31. return result;
  32. };
'
运行