算法训练 | 回溯算法Part3 | 39.组合总和、40.组合总和II、131.分割回文串

devtools/2024/9/21 15:24:34/

目录

39.组合总和

回溯法

40.组合总和II

回溯法

131.分割回文串

回溯法

39.组合总和

  • 题目链接：39. 组合总和 - 力扣（LeetCode）

  • 文章讲解：programmercarl.com

回溯法

  • 解题思路

    • 本题没有数量要求，可以无限重复，但是有总和的限制，所以间接的也是有个数的限制。因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过target，就返回。而在77.组合 (opens new window)和216.组合总和III (opens new window)中都可以知道要递归K层，因为要取k个元素的组合。

  • 解题步骤

    • 递归函数参数：

      • 定义两个全局变量，二维数组result存放结果集，数组path存放符合条件的结果。（这两个变量可以作为函数参数传入）。

      • 题目中给出的参数，集合candidates, 和目标值target。

      • 此外还定义了int型的sum变量来统计单一结果path里的总和，其实这个sum也可以不用，用target做相应的减法就可以了，最后如何target==0就说明找到符合的结果了，但为了代码逻辑清晰，依然用了sum。

      • 本题还需要startIndex来控制for循环的起始位置（什么时候需要startIndex？如果是一个集合来求组合的话，就需要startIndex，例如：77.组合 (opens new window)，216.组合总和III (opens new window)。如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合）

    • 递归终止条件：终止只有两种情况，sum大于target和sum等于target。sum等于target的时候，需要收集结果。

    • 单层搜索的逻辑：单层for循环依然是从startIndex开始，搜索candidates集合。注意本题和77.组合 (opens new window)、216.组合总和III (opens new window)的一个区别是：本题元素为可重复选取的。backtracking不用i+1了，表示可以重复读取当前的数。

  • 代码注意

    • i从索引开始

    • 存入的是数组的元素

  • 代码一：回溯算法

// 版本一
class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {if (sum > target) {return;}if (sum == target) {result.push_back(path);return;}for (int i = startIndex; i < candidates.size(); i++) {sum += candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i); // 不用i+1了，表示可以重复读取当前的数sum -= candidates[i];path.pop_back();}}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {result.clear();path.clear();backtracking(candidates, target, 0, 0);return result;}
};

40.组合总和II

  • 题目链接：leetcode.cn

  • 文章讲解：题目链接/文章讲解：代码随想录

回溯法

  • 解题思路

    • 这道题目和39.组合总和 (opens new window)如下区别：

      • 本题candidates 中的每个数字在每个组合中只能使用一次。

      • 本题数组candidates的元素是有重复的，而39.组合总和 (opens new window)是无重复元素的数组candidates

    • 最后本题和39.组合总和 (opens new window)要求一样，解集不能包含重复的组合。本题的难点在于区别2中：集合（数组candidates）有重复元素，但还不能有重复的组合。

    • 要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。为了理解去重来举一个例子，candidates = [1, 1, 2], target = 3，（方便起见candidates已经排序了）强调一下，树层去重的话，需要对数组排序！

  • 解题步骤

    • 递归函数参数：与39.组合总和 (opens new window)套路相同，此题还需要加一个bool型数组used，用来记录同一树枝上的元素是否使用过。

          这个集合去重的重任就是used来完成的。

    • 递归终止条件：与39.组合总和 (opens new window)相同，终止条件为 sum > target 和 sum == target。

    • 单层搜索的逻辑：

      • 这里与39.组合总和 (opens new window)最大的不同就是要去重了。要去重的是“同一树层上的使用过”，如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。此时for循环里就应该做continue的操作。

      • used[i - 1] == true，说明同一树枝candidates[i - 1]使用过；used[i - 1] == false，说明同一树层candidates[i - 1]使用过。

      • 同一树层，used[i - 1] == false 才能表示，当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。而 used[i - 1] == true，说明是进入下一层递归，去下一个数，所以是树枝上。

  • 代码注意

    • 要定义标记数组，注意数据类型

  • 代码一：回溯剪枝

// 时间复杂度: O(n * 2^n)
// 空间复杂度: O(n)
class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {if (sum == target) {result.push_back(path);return;}for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过// used[i - 1] == false，说明同一树层candidates[i - 1]使用过// 要对同一树层使用过的元素进行跳过if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {continue;}sum += candidates[i];path.push_back(candidates[i]);used[i] = true;backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次used[i] = false;sum -= candidates[i];path.pop_back();}}public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool> used(candidates.size(), false);path.clear();result.clear();// 首先把给candidates排序，让其相同的元素都挨在一起。sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};

131.分割回文串

  • 题目链接：leetcode.cn

  • 文章讲解：代码随想录

回溯法

回文串是向前和向后读都相同的字符串。

  • 解题思路

    • 本题这涉及到两个关键问题：

      • 切割问题，有不同的切割方式

      • 判断回文

    • 切割问题类似组合问题：

      • 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个.....。

      • 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段.....。

    • 递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。

  • 解题步骤

    • 递归函数参数和返回值：

      • 全局变量数组path存放切割后回文的子串，二维数组result存放结果集。 （这两个参数可以放到函数参数里）

      • 本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的。

    • 递归函数终止条件：

      • 切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止条件。

      • 在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。在此处所有path传入result，在传path时再做判断。

    • 单层搜索的逻辑：

      • 在for (int i = startIndex; i < s.size(); i++)循环中，定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。

      • 首先判断这个子串是不是回文，如果是回文，就加入在vector<string> path中，path用来记录切割过的回文子串。

      • 注意切割过的位置，不能重复切割，所以，backtracking(s, i + 1); 传入下一层的起始位置为i + 1。

    • 判断回文子串：可以使用双指针法，一个指针从前向后，一个指针从后向前，如果前后指针所指向的元素是相等的，就是回文字符串了。

  • 代码注意

    • 注意string类型

    • (s, startIndex, i)回文判断区间

    • 截取字符串传入

    • 满足回文只是传入path，回溯在判断外

  • 代码一：回溯算法

// 时间复杂度: O(n * 2^n)
// 空间复杂度: O(n^2)
class Solution {
private:vector<vector<string>> result;vector<string> path; // 放已经回文的子串void backtracking (const string& s, int startIndex) {// 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了if (startIndex >= s.size()) {result.push_back(path);return;}for (int i = startIndex; i < s.size(); i++) {if (isPalindrome(s, startIndex, i)) {   // 是回文子串// 获取[startIndex,i]在s中的子串string str = s.substr(startIndex, i - startIndex + 1);path.push_back(str);} else {                                // 不是回文，跳过continue;}backtracking(s, i + 1); // 寻找i+1为起始位置的子串path.pop_back(); // 回溯过程，弹出本次已经添加的子串}}bool isPalindrome(const string& s, int start, int end) {for (int i = start, j = end; i < j; i++, j--) {if (s[i] != s[j]) {return false;}}return true;}
public:vector<vector<string>> partition(string s) {result.clear();path.clear();backtracking(s, 0);return result;}
};

http://www.ppmy.cn/devtools/45941.html

相关文章

媳妇面试了一家公司，期望月薪20K，对方没多问就答应了，只要求3天内到岗，可我总觉得哪里不对劲。

媳妇面试了一家公司，期望月薪20K，对方没多问就答应了，只要求3天内到岗，可我总觉得哪里不对劲。

“20k&#xff01;明天就来上班吧&#xff01;” 听到这句话&#xff0c;你会不会两眼放光&#xff0c;激动得差点跳起来&#xff1f; 朋友媳妇小丽&#xff0c;最近就经历了这样一场“梦幻面试”。然而&#xff0c;事情的发展却远没有想象中那么美好…… “这公司也太好了吧…
阅读更多...
字节裁员！开启裁员新模式。。

字节裁员！开启裁员新模式。。

最近&#xff0c;互联网圈不太平&#xff0c;裁员消息此起彼伏。而一向以“狼性文化”著称的字节跳动&#xff0c;却玩起了“低调裁员”&#xff0c;用一种近乎“温柔”的方式&#xff0c;慢慢挤掉“冗余”的员工。 “细水长流”&#xff1a;裁员新模式&#xff1f; 不同于以往…
阅读更多...
如何完全清除docker

如何完全清除docker

目录 一、查看相关资源1.查看所有容器2.查看所有镜像3.查看所有未使用的网络4.查看所有未使用的卷 二、清除操作1.停止所有容器2.删除所有容器3.删除所有镜像4.删除所有未使用的网络5.删除所有未使用的卷6.重启Docker服务&#xff08;可选&#xff0c;根据系统和配置可能需要&a…
阅读更多...
do...while循环

do...while循环

基本语法 while循环&#xff0c;是先判断条件再执行。 do...while循环&#xff0c;是先斩后奏&#xff0c;先至少执行一次循环语句块中的逻辑&#xff0c;再判断是否继续。 do {//do while 循环语句块; } while (bool类型的值);注意&#xff1a;do...while语句&#xff0c;存…
阅读更多...
LeetCode-77. 组合【回溯】

LeetCode-77. 组合【回溯】

LeetCode-77. 组合【回溯】 题目描述&#xff1a;解题思路一&#xff1a;回溯背诵版解题思路三&#xff1a;0 题目描述&#xff1a; 给定两个整数 n 和 k&#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1&#xff1a; 输入&a…
阅读更多...
某红书旋转滑块验证码分析与协议算法实现（高通过率）

某红书旋转滑块验证码分析与协议算法实现（高通过率）

文章目录 1. 写在前面2. 接口分析3. 验证轨迹4. 算法还原 【&#x1f3e0;作者主页】&#xff1a;吴秋霖 【&#x1f4bc;作者介绍】&#xff1a;擅长爬虫与JS加密逆向分析&#xff01;Python领域优质创作者、CSDN博客专家、阿里云博客专家、华为云享专家。一路走来长期坚守并致…
阅读更多...
Love-Yi情侣网站3.0存在SQL注入漏洞

Love-Yi情侣网站3.0存在SQL注入漏洞

目录 1. 前言 2. 网站简介 3. 寻找特征点 3.1 第一次尝试 3.2 第二次尝试 4.资产搜索 5.漏洞复现 5.1 寻找漏洞点 5.2 进行进一步测试 5.2.1 手动测试 1.寻找字段 2.寻找回显位 3.查询当前用户 5.2.2 sqlmap去跑 6.总结 1. 前言 朋友说自己建了一个情侣网站,看到…
阅读更多...
python替换“${}“占位符为变量，实现读取配置文件

python替换“${}“占位符为变量，实现读取配置文件

文章目录 背景1、定义正则表达式2、替换变量占位符3、实现功能 背景 使用python编写小工具&#xff0c;有一个配置文件&#xff0c;希望实现类似shell命令的&#xff0c;定义变量并且使用${}或者$来引用。如果有好的建议欢迎讨论。 配置文件示例内容如下: D:\project\test\pr…
阅读更多...
最新文章

Copyright @ 2022~2023