代码随想录Day 23|回溯Part02,39.组合总和、40.组合总和Ⅱ、131.分割回文串

提示:DDU,供自己复习使用。欢迎大家前来讨论~

文章目录

  • 第七章 回溯算法part03
  • 一、题目
    • 题目一: 39. 组合总和
      • 解题思路:
      • 回溯三部曲
      • 剪枝优化
      • 小结:
    • 题目二:40.组合总和Ⅱ
      • 解题思路:
      • 回溯三部曲
    • 题目三: 131.分割回文串
      • 解题思路
      • 回溯三部曲
      • 判断回文子串
      • 优化
  • 总结


第七章 回溯算法part03

开始补一下

一、题目

题目一: 39. 组合总和

39. 组合总和

解题思路:

本题是可以重复被选取,不会出现0,然后看到下面提示:1 <= candidates[i] <= 200,我就放心了。

直接的想法就是两层for循环,依次输出两个元素。

本题搜索的过程抽象成树形结构如下:

39.组合总和

注意图中叶子节点的返回条件,因为本题没有组合数量要求,仅仅是总和的限制,所以递归没有层数的限制,只要选取的元素总和超过target,就返回!

回溯三部曲

排列和组合是不一样的。

本题还需要startIndex来控制for循环的起始位置,对于组合问题,什么时候需要startIndex呢?

如果是一个集合来求组合的话,就需要startIndex,例如77.组合,216.组合总和III 。

如果是多个集合取组合,各个集合之间相互不影响,那么就不用startIndex,例如:17.电话号码的字母组合

  • 递归函数参数
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex)
  • 递归终止条件

在如下树形结构中:

39.组合总和

从叶子节点可以清晰看到,终止只有两种情况,sum大于target和sum等于target。

if (sum > target) {return;
}
if (sum == target) {result.push_back(path);return;
}
  • 单层搜索的逻辑

单层for循环依然是从startIndex开始,搜索candidates集合。

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();        // 回溯
}

完整代码:

// 版本一
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;}
};

剪枝优化

对总集合排序之后,如果下一层的sum(就是本层的 sum + candidates[i])已经大于target,就可以结束本轮for循环的遍历

39.组合总和1

for循环剪枝代码如下:

for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; 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) {result.push_back(path);return;}// 如果 sum + candidates[i] > target 就终止遍历for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {sum += candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i);sum -= candidates[i];path.pop_back();}}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {result.clear();path.clear();sort(candidates.begin(), candidates.end()); // 需要排序backtracking(candidates, target, 0, 0);return result;}
};
  • 时间复杂度: O(n * 2^n),注意这只是复杂度的上界,因为剪枝的存在,真实的时间复杂度远小于此
  • 空间复杂度: O(target)

小结:

  • 组合没有数量要求
  • 元素可以无限重复取

在求和问题中,排序之后加剪枝是常见的套路!

题目二:40.组合总和Ⅱ

40. 组合总和 II

解题思路:

所以我们要去重的是同一树层上的“使用过”,同一树枝上的都是一个组合里的元素,不用去重

强调一下,树层去重的话,需要对数组排序!

下面有used数组的使用:

40.组合总和II

回溯三部曲

  • 确定递归函数参数

依然需要一维数组path来存放符合条件的结果,二维数组result来存放结果集。

此题还需要加一个bool型数组used,用来记录同一树枝上的元素是否使用过。这个集合去重的重任就是used来完成的。

vector<vector<int>> result; // 存放组合集合
vector<int> path;           // 符合条件的组合
void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
  • 确定终止条件
if (sum > target) { // 这个条件其实可以省略return;
}
if (sum == target) {result.push_back(path);return;
}
  • 单层搜索过程

如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false,就说明:前一个树枝,使用了candidates[i - 1],也就是说同一树层使用过candidates[i - 1]

40.组合总和II1

在图中将used的变化用橘黄色标注上,可以看出在candidates[i] == candidates[i - 1]相同的情况下:

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

为什么 used[i - 1] == false 就是同一树层呢,因为同一树层,used[i - 1] == false 才能表示,当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。

而 used[i - 1] == true,说明是进入下一层递归,去下一个数,所以是树枝上,如图所示:

img

注意sum + candidates[i] <= target为剪枝操作

回溯三部曲分析完了,整体C++代码如下:

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;}
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n)

小结:

去重逻辑很关键,涉及到回溯。

题目三: 131.分割回文串

131. 分割回文串

解题思路

本题这涉及到两个关键问题:

  1. 切割问题,有不同的切割方式
  2. 判断回文

例如对于字符串abcdef:

  • 组合问题:选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个…。
  • 切割问题:切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段…。

所以切割问题,也可以抽象为一棵树形结构,如图:

131.分割回文串

递归用来纵向遍历,for循环用来横向遍历,切割线(就是图中的红线)切割到字符串的结尾位置,说明找到了一个切割方法。


回溯三部曲

  • 确定回溯函数参数

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

vector<vector<string>> result;
vector<string> path; // 放已经回文的子串
void backtracking (const string& s, int startIndex) {
  • 确定终止条件
131.分割回文串

从树形结构的图中可以看出:切割线切到了字符串最后面,说明找到了一种切割方法,此时就是本层递归的终止条件。

那么在代码里什么是切割线呢?

在处理组合问题的时候,递归参数需要传入startIndex,表示下一轮递归遍历的起始位置,这个startIndex就是==切割线==。

void backtracking (const string& s, int startIndex) {// 如果起始位置已经大于s的大小,说明已经找到了一组分割方案了if (startIndex >= s.size()) {result.push_back(path);return;}
}
  • 确定单层遍历逻辑

来看看在递归循环中如何截取子串呢?

[startIndex, i] 就是要截取的子串。

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

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();        // 回溯过程,弹出本次已经添加的子串
}

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

判断回文子串

可以使用==双指针法==,一个指针从前向后,一个指针从后向前,如果前后指针所指向的元素是相等的,就是回文字符串了。

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;}

回溯算法模板:

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

完整C++代码:

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;}
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n^2)

优化

  1. 动态规划:动态规划是一种解决子问题重叠问题的有效方法。在判断回文子串的问题中,可以预先计算出一个字符串的所有子串是否为回文,并存储这些结果。这样,在后续的判断中,可以直接查询这些预先计算的结果,而不需要重新计算。
  2. 动态规划的具体实现:可以创建一个二维布尔数组dp[i][j],其中ij分别表示子串的起始和终止索引。如果s[i] == s[j]并且dp[i + 1][j - 1]为真(即s[i + 1]s[j - 1]的子串是回文),则dp[i][j]也为真。这样,对于任意子串,只需要检查一次,并将结果存储在dp数组中。
class Solution {
private:vector<vector<string>> result;vector<string> path; // 放已经回文的子串vector<vector<bool>> isPalindrome; // 放事先计算好的是否回文子串的结果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[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(); // 回溯过程,弹出本次已经添加的子串}}void computePalindrome(const string& s) {// isPalindrome[i][j] 代表 s[i:j](双边包括)是否是回文字串 isPalindrome.resize(s.size(), vector<bool>(s.size(), false)); // 根据字符串s, 刷新布尔矩阵的大小for (int i = s.size() - 1; i >= 0; i--) { // 需要倒序计算, 保证在i行时, i+1行已经计算好了for (int j = i; j < s.size(); j++) {if (j == i) {isPalindrome[i][j] = true;}else if (j - i == 1) {isPalindrome[i][j] = (s[i] == s[j]);}else {isPalindrome[i][j] = (s[i] == s[j] && isPalindrome[i+1][j-1]);}}}}
public:vector<vector<string>> partition(string s) {result.clear();path.clear();computePalindrome(s);backtracking(s, 0);return result;}
};

小结:

列出如下几个难点:

  • 切割问题可以抽象为组合问题
  • 如何模拟那些切割线
  • 切割问题中递归如何终止
  • 在递归循环中如何截取子串
  • 如何判断回文

总结出来难究竟难在哪里也是一种需要锻炼的能力


总结

  • 回溯问题的进阶
  • 判断回文串,可以重复选取元素,使用used数组

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/411620.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【项目源码】终于有人将打字游戏和编程英语结合起来啦!编程初学者的福音

Hello&#xff01;各位彦祖&#xff0c;亦菲们&#xff01;又是美好的一天&#xff01;今天给大家分享一个Java项目源码&#xff1a;Java打字游戏项目源码&#xff01; 看到这里&#xff0c;你可能会说&#xff01; 一个破打字游戏有什么可神气的&#xff01;&#xff01;&…

Leetcode面试经典150题-28.找出字符串第一个匹配项的下标

解法都在代码里&#xff0c;不懂就留言或者私信&#xff0c;比第一题稍微难点 用KMP解这个题简直就像大炮打蚂蚁&#xff0c;但是没办法&#xff0c;现在都是这么卷 package dataStructure.bigFactory;public class _28Strstr {public static int strStr(String s1, String s…

springboot3.x入门系列【5】支持unix sock 套接字服务

目录 一、简介 二、springBoot3.x 套接字的支持 1. 环境要求 2. springboot内置tomcat 2.1 支持unix 设置 unixDomainSocketPath 2.2 windows 下unix服务测试 3. springboot外置tomcat 3.1 tomcat 配置unix socket 套接字 3.2 启动tomcat 服务 3.3 nginx 支持unix…

android13固定app方向 强制app方向

总纲 android13 rom 开发总纲说明 1.前言 经常遇到客户有固定或者设置应用方向,不让他们改成其他方向的需求。今天我们就来处理这种问题。 2.问题分析 在 Android 10 之前,显示旋转的处理逻辑分散在多个类和模块中,Android 10 统一了这些逻辑,集中在 DisplayRotation.ja…

MATLAB 沿任意方向分层点云(82)

MATLAB 沿任意方向分层点云(82) 一、算法介绍二、算法实现1.代码2.效果更多内容参考: MATLAB点云处理学习 一、算法介绍 沿着某个方向,将点云分割为多层,每层点云使用不同颜色进行可视化显示,具体代码和不同方向的分层效果如下: 二、算法实现 1.代码 % Load point c…

【文档合集】软件类常用文档整理大全,软件工程,软件项目管理,技术标书方案,模

目的&#xff1a;规范系统开发流程&#xff0c;提高系统开发效率。 立项申请需求分析方案设计方案评审开发调整测试阶段系统培训试运行测试验收投入使用 所有文档过去进主页获取。 获取方式&#xff1a;本文末个人名片直接获取。 软件资料清单列表部分文档清单&#xff1a;工作…

【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch12 随机森林(Random Forest)

系列文章目录 监督学习&#xff1a;参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归&#xff08;SAheart.csv&#xff09; 【学习笔记】 陈强-机器学习-Python-…

(三)、软硬件全开源手表,具有Wi-Fi和蓝牙LE连接,并可连接互联网,超多表盘。(Watchy)

Watchy 是一款具有开源硬件和软件的 E-Ink watch。它采用准系统设计&#xff0c;利用 PCB 作为表身&#xff0c;可以原样佩戴&#xff0c;或进一步定制不同的 3D 打印表壳和表带。这是一款独特的设计&#xff0c;也是一个可穿戴开发平台&#xff0c;让用户可以创造自己的应用。…

【功能自动化】使用HTMLTestRunner生成测试报告

配置环境&#xff1a; 1.部署webtours网站 2.user.txt 3.HTMLTestRunner.py """ A TestRunner for use with the Python unit testing framework. It generates a HTML report to show the result at a glance.The simplest way to use this is to invoke it…

【论文阅读|cryoET】本周粗读汇总

论文1&#xff1a;CryoDRGN-ET&#xff1a;深度重建生成网络以可视化细胞内动态生物分子 Abstract 虽然冷冻电子断层扫描可以以分子分辨率揭示结构&#xff0c;但图像处理算法仍然是解决原位生物分子结构异质性的瓶颈。本文介绍CryoDRGN-ET用于cryoET断层图的异质重建。CryoD…

Figma 替代品 Penpot 安装和使用教程

在设计领域&#xff0c;Figma 无疑是一个巨人。它彻底改变了设计流程&#xff0c;将协作带到了一个全新的高度。然而&#xff0c;随着 Adobe 收购 Figma 的消息传出&#xff0c;许多设计师和开发者开始担心&#xff1a;Figma 未来会如何演变&#xff1f;那些好用的特性会不会被…

灵办AI:解锁办公新境界,让工作更智能、更高效!

在这个信息爆炸的时代&#xff0c;我们每个人都在寻找能够提升效率、简化工作流程的工具。如果您正在寻找一个能够全方位提升工作效率的AI助手&#xff0c;那么灵办AI绝对值得您的关注。 为什么选择灵办AI&#xff1f; 在众多AI工具中&#xff0c;灵办AI凭借其卓越的性能和独…

简单的C程序基础知识

C程序大致分为3种基本结构&#xff1a; 顺序结构、分支结构、循环结构 由这3种结构可以组成各式各样的复杂程序。 01--C语句 C语句分为以下几类&#xff1a; ①表达式语句 ②函数调用语句 ③控制语句 ④复合语句 ⑤空语句 1.表达式语句&#xff1a; 由表达式分号组成 表…

ArgoWorkflow教程(三)---使用 Artifacts 实现步骤间文件共享

上一篇我们分析了 Workflow、WorkflowTemplate、template 之间的关系。本篇主要分析如何在 argo-workflow 中使用 S3 存储 artifact 实现步骤之间的文件共享。 本文主要解决两个问题&#xff1a; 1&#xff09;artifact-repository 如何配置2&#xff09;Workflow 中如何使用 …

用AppleScript做macOS UI自动化

用AppleScript做macOS UI自动化 一、定位到System Setting → General → Login Items& Extensions 页面1. 获取页面锚点&#xff0c;以便直接滑动到锚点区域2. 滑动到Extensions 区域 二、根据名称找到元素&#xff0c;再点击元素的按钮三、获取元素位置并点击 一、定位到…

Datawhale X 李宏毅苹果书 AI夏令营 Task2笔记

Datawhale X 李宏毅苹果书 向李宏毅学深度学习&#xff08;进阶&#xff09; 是 Datawhale 2024 年 AI 夏令营第五期的学习活动&#xff08;“深度学习 进阶”方向&#xff09; 往期task1链接&#xff1a;深度学习进阶-Task1 我做的task1的笔记博客&#xff1a;传送门 Datawhal…

【C语言】宏定义详解

目录 C语言宏定义详解1. 宏定义关键词总览2. #define3. #undef4. #ifdef5. #ifndef6. #if7. #else8. #elif9. #endif10. #include11. #error12. #pragma12.1 #pragma once12.2 #pragma pack12.3 #pragma warning12.4 #pragma GCC 13. #line14. 字符串化和标识符连接14.1 字符串…

C# 对桌面快捷方式的操作设置开机启动项

首先在项目中引入Windows Script Host Object Model&#xff0c;引入方式如下图。 对于桌面快捷方式的修改无非就是将现有的快捷方式修改和添加新的快捷方式。 1、遍历桌面快捷方式&#xff0c;代码如下。 string desktopPath Environment.GetFolderPath(Environment.Special…

LLM 应用开发入门 - 实现 langchain.js ChatModel 接入火山引擎大模型和实现一个 CLI 聊天机器人(上)

前言 Langchain 是一个大语言模型(LLM)应用开发的框架,提供了 LLM 开发中各个阶段很多非常强大的辅助工具支持。对于进行 LLM 开发是必不可少的工具库。 本文将通过一个实际的开发例子来入门 LLM 开发基础工具链,并实现 langchain.js ChatModel 接入火山引擎大模型和基于…

【亲测有效】linux抓包http协议分析,分析header和body

linux抓包http协议分析&#xff0c;分析header和body 安装&#xff1a; 执行抓包命令&#xff0c;这里ip要换成你想抓包的目标ip&#xff1a; ngrep -q -W byline -d any "^Host:|^GET|^POST|^HTTP/" tcp and host 183.2.172.42 and port 80 触发抓包&#xff0c;…