代码随想录算法训练营第二十三天| 39. 组合总和 40.组合总和II 131.分割回文串

本文主要是介绍代码随想录算法训练营第二十三天| 39. 组合总和 40.组合总和II 131.分割回文串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 一、LeetCode 39. 组合总和
    • 思路:
    • C++代码
  • 二、LeetCode 40.组合总和II
    • 思路
    • C++代码
  • 三、LeetCode 131.分割回文串
    • 思路
    • C++代码
  • 总结


一、LeetCode 39. 组合总和

题目链接:LeetCode 39. 组合总和

文章讲解:代码随想录
视频讲解:带你学透回溯算法-组合总和(对应「leetcode」力扣题目:39.组合总和)| 回溯法精讲!

思路:

 题目要求从给出的数组里选取几个数,使得总和等于给出的target,并且数组中的数可以无限制重复选取,那么相对于前面做过的216. 组合总和 III来说,只需要在每层循环的时候考虑到上次选过的数字可以重复选取即可,即让循环条件中的初始值int i = pre:

for(int i = pre; i < candidates.size(); i++) //pre为上一层选取的数字的下标

 其余的代码基本不变,要找题目要求编程即可。

C++代码

class Solution {
private:vector<vector<int>> comb;vector<int> set;void backtrack(vector<int> candidates, int target, int sum, int pre){//pre记录前一个数字的下标if(sum > target) return; //剪枝操作if(sum == target){if(comb.size() < 150){comb.push_back(set);}return;}for(int i = pre; i < candidates.size(); i++){ //同一个数字可以重复选取,所以可以从下标pre开始取set.push_back(candidates[i]);sum += candidates[i];backtrack(candidates, target, sum, i);sum -= candidates[i];set.pop_back();}}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtrack(candidates, target, 0, 0);return comb;}
};

二、LeetCode 40.组合总和II

题目链接:LeetCode 40.组合总和II

文章讲解:代码随想录
视频讲解:回溯算法中的去重,树层去重树枝去重,你弄清楚了没?| LeetCode:40.组合总和II

思路

 本题的重点在于:每个数字只能选一次,且给出的数组中会出现重复的数字,因此对于解集中的数组需要进行去重操作

 笔者在本题中采用的是在子集生成过程中,对子集树同一层的数进行的去重操作。
在这里插入图片描述
 如图,在子集树的遍历过程中,当数字选取在同一条树支上时,即选取数字都会出现在子集中时,重复数字是可以选取的;而当选取数字在同一树层上时,即在同一个位置上选取数字时,不能重复选取。

 体现在代码中则是当前数字与前一个数字相同,且前一个数字没有被选取时,那么当前的数字就不能选取(因为如果选取,那么后续生成的所有子集都会和选取前一个数生成的子集相同,出现重复),所以我们在递归中加上一个判断条件即可去重。

C++代码

class Solution {
private:vector<vector<int>> comb;vector<int> set;vector<bool> used;int sum;void backtrack(vector<int> candidates, int target, int pre){if(sum == target){comb.push_back(set);return;}for(int i = pre + 1; i < candidates.size() && sum + candidates[i] <= target; i++){if(i > 0 && candidates[i] == candidates[i-1] && !used[i-1]) continue;//遇到同一层相同数字,则跳过此次循环set.push_back(candidates[i]);sum += candidates[i];used[i] = true;backtrack(candidates, target, i);used[i] = false;sum -= candidates[i];set.pop_back();}}
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sum = 0;sort(candidates.begin(), candidates.end());for(auto x: candidates){used.push_back(false);}backtrack(candidates, target, -1);return comb;}
};

三、LeetCode 131.分割回文串

题目链接:LeetCode 131.分割回文串

文章讲解:代码随想录
视频讲解:带你学透回溯算法-分割回文串(对应力扣题目:131.分割回文串)| 回溯法精讲!

思路

 题目要求将给出的字符串划分为几个回文串的组合,笔者采用回溯算法。对于回文串的判断和处理,笔者采用延伸生成的方法,如图:
在这里插入图片描述
 对于一个已经确定的回文串,如果他的左右两边的字符相等的话,那么加上左右两边的字符会变成一个更长的字符串(这一点适用于奇数长度与偶数长度);因此笔者的算法思想为:在当前未确定的字符串部分找到一个最短的回文串,在这个最短回文串的基础上向两边延伸生成新的回文串;于是对于回溯算法的设计即是在每一层对于最短的回文串进行操作。
在这里插入图片描述
 如图,对于每层回溯的递归逻辑,将当前遍历到的字符作为回文串生成的中心位置字符,在此基础上进行延伸;具体延伸方法为:在原回文串基础上,判断原回文串两侧的字符是否相等,如果相等就可以加入到原串两侧,完成延伸,进入下一层for循环继续延伸;否则跳出for循环。

 回溯递归函数的设计依旧是分为三部曲来编写:

 递归函数的传参以及返回值,笔者设计回溯算法无返回值,设置全局变量储存回文串的分割方案;传参方面,由于笔者在递归函数中处理的是回文串最中间的字符,因此需要一个下标记录当前的字符位置,同时需要另一个下标记录回文串可以到达的最左端的位置(用来控制for循环),因此递归的传参和返回为:

void backtrack(int cur, int pre)

 终止条件设计为,递归函数传入的当前字符的位置大于原串的长度,将当前方案存入全局变量中,递归函数返回。

if (cur >= size) {palindrome.push_back(set);return;
}

 递归函数逻辑如下:

 由于该算法中,奇数长度与偶数长度的回文串生成方式有区别,所以需要分开判断延伸的条件:

//延伸条件判断
if (palindrome[0][cur - i] == palindrome[0][cur + i]) //奇数长度回文串if (palindrome[0][cur - i] == palindrome[0][cur + i + 1]) //偶数长度回文串

 由于奇数长度可以直接将当前的字符作为第一个回文串,偶数长度需要进行一次判断才能确定第一个回文串,因此在循环逻辑和循环条件上也有区别,因此奇数长度和偶数长度笔者分成两个for循环来写。

for (int i = 0; i < size - cur && i <= cur - pre; i++) //奇数长度回文串for (int i = 0; i < size - cur - 1 && i <= cur - pre; i++) //偶数长度回文串

for循环中,当满足两端字符相等的延伸条件时,扩展回文串,并且删除前面一个字符(因为前面一个字符被包含进当前的回文串了),进入下一层递归。

 由于本题和笔者算法的特殊性,在递归返回时不直接进行回溯,而是当回文串两端字符不相等时,即不能再延伸出更长的回文串时,将回文串中包含过的左侧的元素依次返还,便于返回上一层递归继续操作:

int b = odd.size() / 2; //遍历完毕,归还前面的元素
for (int j = 0; j < b; j++) {string tmp(1, odd[j]);set.push_back(tmp);
}

C++代码

class Solution {
private:vector<vector<string>> palindrome;vector<string> set;int size;void backtrack(int cur, int pre) {if (cur >= size) {palindrome.push_back(set);return;}string odd = "";string even = "";for (int i = 0; i < size - cur && i <= cur - pre; i++) {//奇数长度回文串if (odd.empty()) {  //奇数个存在一个的情况,除此以外的情况与偶数个类似odd = palindrome[0][cur];set.push_back(odd);backtrack(cur + 1, pre);set.pop_back();}else {if (palindrome[0][cur - i] == palindrome[0][cur + i]) {odd = palindrome[0][cur - i] + odd + palindrome[0][cur - i];set.pop_back();set.push_back(odd);backtrack(cur + i + 1, cur + i + 1);set.pop_back();}else {break;}}}int b = odd.size() / 2; //遍历完毕,归还前面的元素for (int j = 0; j < b; j++) {string tmp(1, odd[j]);set.push_back(tmp);}for (int i = 0; i < size - cur - 1 && i <= cur - pre; i++) {if (palindrome[0][cur - i] == palindrome[0][cur + i + 1]) { //偶数长度回文串even = palindrome[0][cur - i] + even + palindrome[0][cur - i];if (i > 0) set.pop_back();set.push_back(even);backtrack(cur + i + 2, cur + i + 2);set.pop_back();}else {break;}}b = (even.size() / 2) - 1; //遍历完毕,归还元素for (int j = 0; j < b; j++) {string tmp(1, even[j]);set.push_back(tmp);}}
public:vector<vector<string>> partition(string s) {size = s.size();for (auto x : s) { //构建一个初始集合,便于生成string pal;pal.push_back(x);set.push_back(pal);}palindrome.push_back(set);set.clear();backtrack(0, 0);palindrome.erase(palindrome.begin()); //构建的初始集合和生成的第一个集合重复,因此需要删除一个(可优化)return palindrome;}
};


总结

 回溯法的进阶应用。在编写回溯算法时仍要注意递归的逻辑结构、终止条件和剪枝条件、循环的边界条件,以及递归返回时数值的恢复(回溯),都是回溯算法的重点问题。


文章图片来源:代码随想录 (https://programmercarl.com/)

这篇关于代码随想录算法训练营第二十三天| 39. 组合总和 40.组合总和II 131.分割回文串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1115725

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时