首页 > 编程语言 >「代码随想录算法训练营」第十九天 | 回溯算法 part01

「代码随想录算法训练营」第十九天 | 回溯算法 part01

时间:2024-07-24 15:57:20浏览次数:17  
标签:return part01 res 随想录 back int 算法 vector backtracking

回溯算法模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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

77. 组合

题目链接:https://leetcode.cn/problems/combinations/
题目难度:中等
文章讲解:https://programmercarl.com/0077.组合.html
视频讲解:https://www.bilibili.com/video/BV1ti4y1L7cv
题目状态:自己没思路,学习回溯

思路:

使用回溯三部曲:

  1. 参数与返回值:参数是nk以及startIndex(确保没有回到前面再次遍历),返回值为void
  2. 终止条件:当单层循环保存到vector<int>中的内容等于k时,单层终止,此时需要将该数组push_back到结果集里面。
  3. 单层循环:一个for循环,每次循环到一个内容时,push_back到当前循环的数组中,之后递归下一个循环,并且将自己pop_back出数组。

代码:

class Solution {
public:
    vector<vector<int>> res;
    vector<int> vec;
    void backtracking(int n, int k, int startIndex) {
        if(vec.size() == k) {
            res.push_back(vec);
            return;
        }
        for(int i = startIndex; i <= n; ++i) {
            vec.push_back(i);
            backtracking(n, k, i + 1);
            vec.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return res;
    }
};

剪枝优化代码:(主要剪枝的内容就是看剩下遍历的内容是否还够,如果不够就不需要遍历了)

class Solution {
public:
    vector<vector<int>> res;
    vector<int> vec;
    void backtracking(int n, int k, int startIndex) {
        if(vec.size() == k) {
            res.push_back(vec);
            return;
        }
        for(int i = startIndex; i <= n - (k - vec.size()) + 1; ++i) {
            vec.push_back(i);
            backtracking(n, k, i + 1);
            vec.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return res;
    }
};

216. 组合总和III

题目链接:https://leetcode.cn/problems/combination-sum-iii/
题目难度:中等
文章讲解:https://programmercarl.com/0216.组合总和III.html
视频讲解:https://www.bilibili.com/video/BV1wg411873x
题目状态:通过,但是没有思考到剪枝优化的方法,学习学习

思路:

和上一题没什么区别,就是在单层循环中加入了一个加减操作。

代码:

class Solution {
public:
    vector<vector<int>> res;
    vector<int> vec;
    void backtracking(int k, int n, int startIndex) {
        if(vec.size() == k && n == 0) {
            res.push_back(vec);
            return;
        }
        for(int i = startIndex; i <= 9; ++i) {
            vec.push_back(i);
            n -= i;
            backtracking(k, n, i + 1);
            vec.pop_back();
            n += i;
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k, n, 1);
        return res;
    }
};

剪枝优化是用过加入一个参数实现的,代码如下:

class Solution {
private:
    vector<vector<int>> result; // 存放结果集
    vector<int> path; // 符合条件的结果
    void backtracking(int targetSum, int k, int sum, int startIndex) {
        if (sum > targetSum) { // 剪枝操作
            return; 
        }
        if (path.size() == k) {
            if (sum == targetSum) result.push_back(path);
            return; // 如果path.size() == k 但sum != targetSum 直接返回
        }
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝
            sum += i; // 处理
            path.push_back(i); // 处理
            backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
            sum -= i; // 回溯
            path.pop_back(); // 回溯
        }
    }

public:
    vector<vector<int>> combinationSum3(int k, int n) {
        result.clear(); // 可以不加
        path.clear();   // 可以不加
        backtracking(n, k, 0, 1);
        return result;
    }
};

17. 电话号码的字母组合

题目链接:https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
题目难度:中等
文章讲解:https://programmercarl.com/0017.电话号码的字母组合.html
视频讲解:https://www.bilibili.com/video/BV1wg411873x
题目状态:没思路,看题解

思路:

还是使用回溯,直接看代码更易懂。

代码:

class Solution {
public:
    const string letterMap[10] = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    vector<string> res;
    string s;
    void backtracking(const string& digits, int idx) {
        if(idx == digits.size()) {
            res.push_back(s);
            return;
        }
        int digit = digits[idx] - '0';
        string letters = letterMap[digit];
        for(int i = 0; i < letters.size(); ++i) {
            s.push_back(letters[i]);
            backtracking(digits, idx + 1);
            s.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0) return res;
        backtracking(digits, 0);
        return res;
    }
};

标签:return,part01,res,随想录,back,int,算法,vector,backtracking
From: https://www.cnblogs.com/frontpen/p/18321088

相关文章

  • 最小生成树(Kruskal和Prim算法)
    最小生成树(Kruskal和Prim算法)部分资料来源于:最小生成树(Kruskal算法)_kruskal算法求最小生成树-CSDN博客、【算法】最小生成树——Prim和Kruskal算法-CSDN博客关于图的几个概念定义:连通图:在无向图中,若任意两个顶点vi与vj都有路径相通,则称该无向图为连通图。强连通图:在有向......
  • 24暑假算法刷题 | Day20 | LeetCode 235. 二叉搜索树的最近公共祖先,701. 二叉搜索树中
    目录235.二叉搜索树的最近公共祖先题目描述题解701.二叉搜索树中的插入操作题目描述题解450.删除二叉搜索树中的节点题目描述题解235.二叉搜索树的最近公共祖先点此跳转题目链接题目描述给定一个二叉搜索树,找到该树中两个指定节点的最近公共祖先。百度......
  • 24暑假算法刷题 | Day21 | LeetCode 669. 修剪二叉搜索树,108. 将有序数组转换为二叉搜
    目录669.修剪二叉搜索树题目描述题解108.将有序数组转换为二叉搜索树题目描述题解538.把二叉搜索树转换为累加树题目描述题解669.修剪二叉搜索树点此跳转题目链接题目描述给你二叉搜索树的根节点root,同时给定最小边界low和最大边界high。通过修剪二叉......
  • 代码随想录算法训练营第八天|● 344.反转字符串● 541. 反转字符串II● 卡码网:54.替换
    题目:344.反转字符串编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用O(1)的额外空间解决这一问题。示例1:输入:s=["h","e","l","l","o"]输出:["o","l","l","e",&......
  • ADAU1761的AVC音效算法详解(Automatic Volume Control)
    作者的话AVC,AutomaticVolumeControl,自动音量控制,这是一个很有特点的算法,我们来看看他在哪里?怎么去用。硬件准备ADAU1761开发板产品链接:https://item.taobao.com/item.htm?spm=a1z10.5-c.w4002-5192690539.11.28686332WA8nC3&id=38240607959USBi仿真器产品链接:https:......
  • 代码随想录 day8 || 344 反转字符串 541 反转字符串|| 54 替换数字
    344反转字符串funcreverseString(s[]byte){ //思路思考双指针 left,right:=0,len(s)-1 forleft<right{ s[left],s[right]=s[right],s[left] left++ right-- }}//ez没啥好说的时间n/2=n空间1541反转字符串||funcreverseStr(sstring......
  • [杂项] [算法] [数据结构] 暑期专题狂补
    或曰,有学长两天授吾以十专题,吾顿感日月之紧迫,以专题竟不能以吾之所有,遂成此文,以记之语文确实没学好本文可能涵盖多个知识点,故每个的讲解比较简略,仅供参考一.2-SAT$2-SAT$用于求解一个变量只有两种情况的适应性问题(就是有没有解以及输出一种方案);其实可以类比二分图最大......
  • 基于完美反射假设的自动白平衡算法
    简介完美反射假设(PerfectReflectorAssumption)是另一种常见的自动白平衡(AWB)方法。它假设图像中有一些物体具有完美反射特性,能够反射所有入射光。这意味着这些物体的反射光应该是白色或灰色,通过识别这些物体并调整图像的色彩平衡,可以实现白平衡。原理完美反射假设的核心思想......
  • 代码随想录算法训练营第41天 |322.零钱兑换、279.完全平方数、139.单词拆分、多重背包
    322.零钱兑换https://leetcode.cn/problems/coin-change/description/代码随想录https://programmercarl.com/0322.零钱兑换.html#算法公开课279.完全平方数https://leetcode.cn/problems/perfect-squares/description/代码随想录https://programmercarl.com/0279.完全平......
  • 代码随想录算法训练营第40天 | 完全背包问题:完全背包基础理论、518.零钱兑换II、377.
    完全背包基础理论https://programmercarl.com/背包问题理论基础完全背包.html#其他语言版本卡码网完全背包例题https://kamacoder.com/problempage.php?pid=1052518.零钱兑换IIhttps://leetcode.cn/problems/coin-change-ii/description/代码随想录https://programmercarl......