代码随想录day23 ||39组合总和1 40组合总和2 131分割回文串

39组合总和1

力扣题目链接

题目描述:

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。 

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

示例 1:

输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。

示例 2:

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3:

输入: candidates = [2], target = 1
输出: []

代码(自己的想法)

class Solution {
public:vector<vector<int>> result;vector<int> path;int sumfunc(vector<int> path){int sum=0;for(auto i:path){sum+=i;}return sum;}void backtracking(int startindex,int target,vector<int>& candidates){if(sumfunc(path)>target){return;}if(sumfunc(path)==target){result.push_back(path);return;}for(int i=startindex;i<candidates.size();i++){path.push_back(candidates[i]);backtracking(i,target,candidates);path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(0,target,candidates);return result;}
};

更官方的代码:

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(int startindex,int target,vector<int>& candidates,int sum){if(sum>target){return;}if(sum==target){result.push_back(path);return;}for(int i=startindex;i<candidates.size();i++){path.push_back(candidates[i]);sum+=candidates[i];backtracking(i,target,candidates,sum);sum-=candidates[i];path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {int sum=0;backtracking(0,target,candidates,sum);return result;}
};

40组合总和2

力扣题目链接

题目描述:

给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

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

注意:解集不能包含重复的组合。 

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

代码:

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分割回文串

力扣题目链接

题目描述:

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 

回文串

 。返回 s 所有可能的分割方案。

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 2:

输入:s = "a"
输出:[["a"]]
class Solution  { 
private:  vector<vector<string>> result; // 存放最终结果  vector<string> path; // 存放当前回文子串  // 回溯函数,参数为原始字符串和当前起始位置  void backtracking (const string& s, int startIndex)  { // 如果起始位置已经大于原始字符串的大小,说明已经找到了一组分割方案  if (startIndex >= s.size()) {  // 将当前 path 存入 result  result.push_back(path);  return;  }// 循环所有可能的结束位置  for (int i = startIndex; i < s.size(); i++)  { // 判断是否是回文子串  if (isPalindrome(s, startIndex, i))  {  // 是回文子串  // 获取[startIndex,i]在原始字符串中的子串  string str = s.substr(startIndex, i - startIndex + 1);  // 将子串存入 path  path.push_back(str);  }else {                                // 不是回文,跳过  continue; }// 递归回溯,寻找下一个回文子串  backtracking(s, 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.rhkb.cn/news/383933.html

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

相关文章

谷粒商城实战笔记-54-商品服务-API-三级分类-拖拽效果

文章目录 一&#xff0c;54-商品服务-API-三级分类-修改-拖拽效果1&#xff0c;el-tree控件加上允许拖拽的属性2&#xff0c;是否允许拖拽3&#xff0c;完整代码 一&#xff0c;54-商品服务-API-三级分类-修改-拖拽效果 本节的主要内容是给三级分类树形结构加上拖拽功能&#…

四、GD32 MCU 常见外设介绍 (4) EXTI 中断介绍

4.EXTI 中断介绍 EXTI(中断/事件控制器)包含多个相互独立的边沿检测电路并且能够向处理器内核产生中断请求或唤醒事件。 EXTI 有三种触发类型&#xff1a;上升沿触发、下降沿触发和任意沿触发。 EXTI中的每一个边沿检测电路都可以独立配置和屏蔽。 4.1.GD32 EXTI 外设原理简介…

如何使用C#自制一个Windows安装包

原文链接&#xff1a;https://www.cnblogs.com/zhaotianff/p/17387496.html 以前都在用InstallShield制作安装包&#xff0c;基本需求是能满足的&#xff0c;但也有一些缺点&#xff1a; 1、界面不能完全定制 2、不能直接调用代码里的功能 平常使用一些其它软件&#xff0c;…

【基础算法总结】优先级队列

优先级队列 1.最后一块石头的重量2.数据流中的第 K 大元素4.前K个高频单词4.数据流的中位数 点赞&#x1f44d;&#x1f44d;收藏&#x1f31f;&#x1f31f;关注&#x1f496;&#x1f496; 你的支持是对我最大的鼓励&#xff0c;我们一起努力吧!&#x1f603;&#x1f603; 1…

FPGA开发——LED流水灯实现先从左往右流水,再从右往左流水

一、概述 我们在设计完一个方向的流水灯的设计时&#xff0c;总是会想实现让流水灯倒着流水回去的设计&#xff0c;这里我也是一样&#xff0c;实现这种设计的方法有很多种&#xff0c;其中就有直接使用case语句将所有可能包含进去编写&#xff0c;这种设计方法是最简单的&…

leetcode日记(51)不同路径Ⅱ

和上一道题&#xff08;无障碍物的最短路径&#xff09;很像&#xff0c;但事实上比上一题多了优化方法 根据上一题改的代码如下&#xff0c;添加了对障碍物的判定&#xff0c;如果有障碍物则将数组值设为0。 class Solution { public:int uniquePathsWithObstacles(vector&l…

Origin制作线性拟合回归图

选中数据&#xff0c;点下方散点图 调整散点颜色 在分析中打开线性拟合回归 添加文本 显示上轴

算法 —— 暴力枚举

目录 循环枚举 P2241 统计方形&#xff08;数据加强版&#xff09; P2089 烤鸡 P1618 三连击&#xff08;升级版&#xff09; 子集枚举 P1036 [NOIP2002 普及组] 选数 P1157 组合的输出 排列枚举 P1706 全排列问题 P1088 [NOIP2004 普及组] 火星人 循环枚举 顾名思…

keil调试SH79F7416

仿真器JET51A, 调试设置 选择器件 再次点击调试就一切正常啦

快速汇总公司产品涉及的项目(服务、站点)

文章目录 引言I 快速汇总公司产品涉及的项目II 常用工具jar包转成exe应用远程操作常用命令III 把应用做成windows服务在后台运行借助工具`instsrv.exe`和`srvany.exe`把应用做成windows服务的步骤SysWOW64 文件夹的作用引言 需求:汇总 平台涉及站点和服务信息 I 快速汇总公司…

SkyWalking入门搭建【apache-skywalking-apm-10.0.0】

Java学习文档 视频讲解 文章目录 一、准备二、服务启动2-1、Nacos启动2-2、SkyWalking服务端启动2-3、SkyWalking控制台启动2-4、自定义服务接入 SkyWalking 三、常用监控3-1、服务请求通过率3-2、服务请求拓扑图3-3、链路 四、日志配置五、性能剖析六、数据持久化6-1、MySQL持…

MySQL SQL 编程练习

目录 创建表并插入数据 查看表结构 创建触发器 创建INSERT 触发器 创建DELETE 触发器 创建更新触发器 创建存储过程 创建提取emp_new表所有员工姓名和工资的存储过程s1 创建存储过程s2&#xff0c;实现输入员工姓名后返回员工的年龄 创建一个存储过程s3&#xff0c;有2个参数&…

Pytorch使用教学5-视图view与reshape的区别

有同学后台留言问为什么view有时可对张量进行形变操作&#xff0c;有时就会报错&#xff1f;另外它和reshape功能好像一致&#xff0c;有什么区别呢&#xff1f;本文就带你了解PyTorch中视图的概念。 在PyTorch中对张量进行形变操作时&#xff0c;很多同学也会使用view方法&am…

3.2、数据结构-数组、矩阵和广义表

数组结构 数组是定长线性表在维度上的扩展,即线性表中的元素又是一个线性表。N维数组是一种“同构”的数据结构,其每个数据元素类型相同、结构一致。 一个m行n列的数组表示如下: 其可以表示为行向量形式&#xff08;一行一行的数据&#xff09;或者列向量形式&#xff08;一…

Windows搭建Nginx代理本地盘的文件 共享本地文件

一、查询自己的内网IP和外网IP的方法&#xff0c;以及判断是否直接连接到公网 内网IP&#xff0c;即局域网IP&#xff1a; 打开cmd窗口&#xff0c; 输入 ipconfig 后回车 外网IP&#xff0c;即公网IP&#xff1a; 打开cmd窗口&#xff0c;输入curl ifconfig.me指令访问ifconfi…

PE文件(十二)导入表

导入表 导入表的引入 当一个PE文件&#xff08;如.dll/.exe等&#xff09;需要使用别的模块的函数&#xff0c;也叫做依赖某模块&#xff0c;就需要一个清单来记录使用的模块&#xff08;一般为.dll文件&#xff0c;为方便理解&#xff0c;以后我们将模块都认为是.dll文件&am…

Python写UI自动化--playwright(通过UI文本匹配实现定位)

本篇简单拓展一下元素定位技巧&#xff0c;通过UI界面的文本去实现定位 目录 匹配XPath 匹配文本元素 .count()统计匹配数量 处理匹配文本返回多个元素 1、使用.nth(index)选择特定元素: 2、获取所有匹配的元素并遍历: 3、错误处理: 匹配XPath 比如我们要定位到下图的…

VScode连接虚拟机运行Python文件的方法

声明&#xff1a;本文使用Linux发行版本为rocky_9.4 目录 1. 在rocky_9.4最小安装的系统中&#xff0c;默认是没有tar工具的&#xff0c;因此&#xff0c;要先下载tar工具 2. 在安装好的vscode中下载ssh远程插件工具 3. 然后连接虚拟机 4. 查看python是否已经安装 5. 下载…

Linux网络:传输层协议TCP(一)

目录 一、TCP协议的定义 二、确认应答机制ACK 三、序号、确认序号 四、超时重传机制 一、TCP协议的定义 TCP 全称为 "传输控制协议(Transmission Control Protocol"). 人如其名, 要对数据的传 输进行一个详细的控制; TCP 协议段格式 • 源/目的端口号: 表示数据…

减轻幻觉新SOTA,7B模型自迭代训练效果超越GPT-4,上海AI lab发布

LLMs在回答各种复杂问题时&#xff0c;有时会“胡言乱语”&#xff0c;产生所谓的幻觉。解决这一问题的初始步骤就是创建高质量幻觉数据集训练模型以帮助检测、缓解幻觉。 但现有的幻觉标注数据集&#xff0c;因为领域窄、数量少&#xff0c;加上制作成本高、标注人员水平不一…