代码随想录训练营Day 29|力扣39. 组合总和、40.组合总和II、131.分割回文串

1.组合总和

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

视频讲解:带你学透回溯算法-组合总和(对应「leetcode」力扣题目:39.组合总和)| 回溯法精讲!_哔哩哔哩_bilibili

代码:(未剪枝版 )

class Solution {
private:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& candidates,int target,int startIndex){// 递归出口if(target < 0){return;}if(target == 0){result.push_back(path);return;}// 处理结点for(int i = startIndex;i < candidates.size();i++){target -= candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,i);path.pop_back();target += candidates[i];}}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {if(candidates.size() == 0) return result;backtracking(candidates,target,0);return result;}
};

 代码:(剪枝版)

class Solution {
private:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& candidates,int target,int startIndex){// 递归出口if(target < 0){return;}if(target == 0){result.push_back(path);return;}// 处理结点// 这里加了判断:如果下一轮的target已经小于0了,就没有必要递归了for(int i = startIndex;i < candidates.size() && target - candidates[i] >= 0;i++){target -= candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,i);path.pop_back();target += candidates[i];}}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {if(candidates.size() == 0) return result;sort(candidates.begin(), candidates.end()); // 涉及大小的剪枝必排序backtracking(candidates,target,0);return result;}
};

思路:学到了这种元素数量不限制的取的解法

其实startIndex变量还是要有,因为我们求的是组合,要数层去重;并且这是在同一个数组里取数。

而数量不限,体现在我在递归里传入的starIndex的值是i,而不是i+1了。之前说过for循环管控每一层数的宽度;递归则管控数的深度。这样更改后,就可以在取完一个数的情况后,继续取这个数。实现如下图所示的效果:

关于剪枝的操作。这种涉及到总和大小的取值时。剪枝就要将给定的数组排序! 而且要注意给定的数组元素里全是正数,只有正数才越加越大。

这道题,我直接用目标总和target取减去每一个结点的数值了,看最后是否被减为0了。

2.组合总和2 

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

视频讲解:回溯算法中的去重,树层去重树枝去重,你弄清楚了没?| LeetCode:40.组合总和II_哔哩哔哩_bilibili

 代码:去重且剪枝过的

class Solution {
private:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& candidates,int target,int startIndex,vector<bool>& used){if(target < 0){return;}if(target == 0){result.push_back(path);return;}for(int i = startIndex;i < candidates.size() && target - candidates[i] >= 0;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;} // 数层去重used[i] = true;target -= candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,i + 1,used);path.pop_back();target += candidates[i];used[i] = false;}}
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool> used(candidates.size(),false);sort(candidates.begin(),candidates.end());backtracking(candidates,target,0,used);return result;}
};

思路:

这道题和上题的区别是:

每个元素只能使用一次——startIndex为i+1;

给定的元素有重复值,但是要去重后的结果:这里就是难点。首先去重是有两个维度的。

 一个组合里可以有相同大小的不同元素,所以递归操作里不需要去重,即上图的同一个子树的数枝上不需要去重;不同组合不能相同,所以要在数层去重。

这里用一个数组used来记录,遇到的和前一个元素相同的情况(这里去重先去把给定数组排序)时,到底是和前一个相同元素是在同一个树枝里的,还是同一个树层里的。

在同一个树枝里:前一个元素已经加入到了path里,已经使用过了。

在同一个树层里:前一个元素没有加入到path里,没有被使用,这是独立的两个分支。

所以如果遇到这种树层里重复的情况,加个判断语句,直接continue(因为接下来的情况还有我们要收集的,所以只是跳过这一种情况,用continue)

3.分割回文串

代码随想录

视频讲解:带你学透回溯算法-分割回文串(对应力扣题目:131.分割回文串)| 回溯法精讲!_哔哩哔哩_bilibili

 代码:

class Solution {
private:vector<string> path;vector<vector<string>> result;bool isPalindrome(string& s,int start,int end){while(start <= end){if(s[start] != s[end]){return false;}start++;end--;}return true;}void backtracking(string& s,int startIndex){// 递归出口if(startIndex >= s.size()){result.push_back(path);return;}// 遍历结点// 回文子串的范围是[startIndex,i]for(int i = startIndex;i < s.size();i++){// 在这里直接判断是否子串满足回文子串if(isPalindrome(s,startIndex,i)){string str = s.substr(startIndex,i - startIndex + 1);path.push_back(str);}else{continue;}backtracking(s,i + 1);path.pop_back();}}
public:vector<vector<string>> partition(string s) {if(s.size() == 0) return result;backtracking(s,0);return result;}
};

思路:

关于substr函数:

这道题很巧妙地将startIndex作为了子串的开始下标,子串的范围可以表示为[startIndex,i]。

同时,本题将判断条件放在了for循环的里面来判断,来决定是否要执行下面的递归回溯操作。判断用了一个额外的函数来判断回文子串。 

细节问题其实就这些。

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

ue引擎游戏开发笔记(38)——实现敌人接收攻击伤害,并作出反应

1.需求分析&#xff1a; 现在已经显示造成实际伤害&#xff0c;但敌人对实际伤害并未产生反馈&#xff0c;例如还击&#xff0c;或者死亡倒地等等&#xff0c;实现敌人对于受击的反馈。 2.操作实现&#xff1a; 1.思路&#xff1a;在动画蓝图中添加死亡动画&#xff0c;并通过…

惠普打印机无线网络连接设置

休息一下&#xff0c;灌个水。这次没多少内容&#xff0c;具体步骤惠普官网上都有&#xff0c;唯一增加的是对安装过程中踩的坑做了一个说明。 一&#xff0e;打印机无线网络连接设置步骤 惠普打印机设置无线网络连接&#xff0c;共16个步骤。 1. 在电脑上打开任意浏览器&am…

速度与激情:Redis如何以核心数据结构驱动极致性能

关注微信公众号 “程序员小胖” 每日技术干货&#xff0c;第一时间送达&#xff01; 引言 Redis是一个开源的内存数据结构存储系统&#xff0c;它支持多种类型的数据结构&#xff0c;如字符串、散列、列表、集合、有序集合等。Redis以其出色的性能和低延迟特性而闻名&#xf…

全网最简单的Mysql 8.3 安装及环境配置教程

Windows系统计算机环境配置 第一篇关于环境配置的文档之MySQL 8.3&#xff08;msi版本和zip版本略有不同&#xff0c;本文档介绍msi版本&#xff0c;若zip版本有需求&#xff0c;请在评论区留言&#xff0c;我后续会出相关文档。&#xff09; 前言 网上的MySQL配置教程非常多…

电脑常用的PDF阅读器-嗨动PDF编辑器!带你详细了解它

电脑常用的PDF阅读器-嗨动PDF编辑器&#xff01;在数字化信息爆炸的时代&#xff0c;PDF格式的文件因其易于打印和保留原始格式等优点&#xff0c;成为了人们日常工作和学习的常用格式。而对于PDF文件的处理&#xff0c;一款功能强大、操作简便的PDF阅读器是必不可少的。今天&a…

合并K个升序链表

题目 解法一 优先级队列 思想 将每个链表中的一个节点存放到优先级队列中&#xff0c;本题采用小根堆&#xff0c;将小根堆中的根节点取出&#xff0c;插入到最终的链表中&#xff0c;并且将该节点在原链表中的下一个节点插入小根堆中&#xff08;需要向下调整&#xff09;&a…

【练习】分治--快排思想

&#x1f3a5; 个人主页&#xff1a;Dikz12&#x1f525;个人专栏&#xff1a;算法(Java)&#x1f4d5;格言&#xff1a;吾愚多不敏&#xff0c;而愿加学欢迎大家&#x1f44d;点赞✍评论⭐收藏 目录 颜色分类 题目描述 题解 代码实现 排序数组 题目描述 题解 代码…

华为正式放弃高通芯片 | 百能云芯

5月15日&#xff0c;据外媒最新报道&#xff0c;高通公司正式确认&#xff0c;华为已无需依赖其处理器供应。 在出口许可被正式吊销前&#xff0c;高通的首席财务官已公开表示&#xff0c;预计明年与华为之间的芯片销售将为零&#xff0c;因为华为决定不再从高通购买4G芯片。 报…

策略模式详解

策略模式 1 概述 先看下面的图片&#xff0c;我们去旅游选择出行模式有很多种&#xff0c;可以骑自行车、可以坐汽车、可以坐火车、可以坐飞机。 作为一个程序猿&#xff0c;开发需要选择一款开发工具&#xff0c;当然可以进行代码开发的工具有很多&#xff0c;可以选择Idea进…

信创改造2---java集成TongLink/Q

上一篇针对TongLINK/Q的安装部署 http://t.csdnimg.cn/9ss7l ,这篇具体说明java集成 1. 准备工作 根据实际修改连接URL等信息 vim TLQ8/etc/tlqjndi.conf 2. JAVA集成 将TongJMS.jar加载到自己的项目中 发送消息 package com.keyou.proj.authentication.service.utils;…

C++11 新特性 常量表达式 constexpr

为了解决常量无法确定的问题&#xff0c;C11在新标准中提出了关键字constexpr&#xff0c;它能够有效地定义常量表达式&#xff0c;并且达到类型安全、可移植、方便库和嵌入式系统开发的目的。 一、常量的不确定性 在C11标准以前&#xff0c;我们没有一种方法能够有效地要求一…

ModuleNotFoundError: No module named ‘openpyxl‘的解决方案

问题描述&#xff1a; ModuleNotFoundError: No module named ‘openpyxl’ 这个错误表示你的 Python 环境中没有安装 openpyxl 这个模块。openpyxl 是一个用于读写 Excel 2010 xlsx/xlsm/xltx/xltm 文件的 Python 库。 解决方案&#xff1a; 要解决这个问题&#xff0c;你需…

Java后端面试常见问题

Java后端面试 经历了两个月的面试和准备&#xff0c;下面对常见的八股文进行总结。有些问题是网上看到的面经里提到的&#xff0c;有些是我真实面试过程遇到的。 异常 1、异常分为哪几种&#xff1f;他们的父类是什么&#xff1f; 注意&#xff1a;所有异常对象的父类为Thr…

做简单易用的GIS资源管理软件

在室外资源管理领域&#xff0c;采用基于GIS的解决方案已成为主流趋势&#xff0c;旨在实现资源的高效利用和管理。GIS技术结合资源对象的规划、定位和监控&#xff0c;为企业提供全面的管理方案&#xff0c;从而优化资源使用、提高运营效率和降低成本。 然而&#xff0c;许多资…

OpenAI新模型GPT-4o“炸裂登场” 响应速度堪比真人 关键还免费!

GPT-4o模型基于来自互联网的大量数据进行训练&#xff0c;更擅长处理文本和音频&#xff0c;并且支持50种语言。更值得一提的是&#xff0c;GPT-4o最快可以在232毫秒的时间内响应音频输入&#xff0c;几乎达到了人类的响应水平。 GPT-4o有多“炸裂”&#xff1f;核心能力有三 G…

网工内推 | 测试工程师,NA认证以上,15薪,补充医疗险

01 天视通 招聘岗位&#xff1a;测试工程师 职责描述&#xff1a;1、网络视频监控相关软件产品测试&#xff0c;及行测试记录和相应各种文档资料/手册编写&#xff1b;2、负责编写测试计划、测试用例、搭建测试环境、执行测试&#xff1b;3、进行BUG验证根据测试结果&#xff…

光伏行业该如何起步?

随着全球对可再生能源的需求日益增长&#xff0c;光伏行业作为其中的佼佼者&#xff0c;正迎来前所未有的发展机遇。然而&#xff0c;对于新进入者或希望在这一领域有所建树的企业来说&#xff0c;如何起步并稳健发展是一个值得深思的问题。以下是一些关于光伏行业起步的建议。…

新手也能看懂的前端单元测试框架:Vitest

单元测试的概念及作用 1.什么是单元测试&#xff1f; 单元测试是测试中的一个重要环节&#xff0c;它针对软件中的最小可测试单元进行验证&#xff0c;通常是指对代码中的单个函数、方法或模块进行测试。 单元测试旨在确定特定部分代码的行为是否符合预期&#xff0c;通过针…

中青杯全国大学生数学建模竞赛纳入多所高校学科竞赛认定目录

2024年第六届中青杯全国大学生数学建模竞赛将于2024年5月23日17:00至5月26日17:00举行,中青杯全国大学生数学建模竞赛是中国高校学科竞赛中规模较大、影响较广的学科竞赛之一,并且纳入多所高校学科竞赛认定目录。 报名截止时间:2024年5月23日12:00 报名网站:http://www.c…

FPGA - GTX收发器-K码 以及 IBERT IP核使用

一&#xff0c;前言 在FPGA - Xilinx系列高速收发器---GTX中详细介绍了GTX的基础知识&#xff0c;以及IP核的调用&#xff0c;下面将补充一下GTX在使用中的高速串行数据流在接收和发送时的控制与对齐&#xff08;K码&#xff09;&#xff0c;以及高速接口GTX&#xff0c;如果G…