LeetCode算法题解(回溯)|39. 组合总和、40. 组合总和 II、131. 分割回文串
一、39. 组合总和
题目链接:39. 组合总和
题目描述:
给你一个 无重复元素 的整数数组 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
输出: []
提示:
1 <= candidates.length <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同1 <= target <= 40
算法分析:
利用经典的回溯算法。
首先创建一个二维数组用来存放所有组合的结果集,以及一个用来遍历每种合理组合的一维数组。
然后调用递归,纵向遍历组合,
传递参数:无重复数组,遍历数组的起始下标。
递归结束条件:当组合中的总和等于目标值时,将组合放入结果集,然后返回,如果组合中的总和大于目标值,则直接返回结束递归。
从起始下标横向遍历无重复数组,candidates[i]插入组合,总和sum加上candidates[i]的值,然后递归判断该组合是否满足,最后再回溯,将candidates[i]从组合中拿出来,sum减去candidates[i]的值,然后进行下一层for循环。
代码如下:
class Solution {List<List<Integer>>result = new ArrayList<>();//用来存放所有组合的结果集LinkedList<Integer> path = new LinkedList<>();//用来遍历每种组合的一维数组int T;//将目标整数定义在全局区域int sum;//记录组合总和int len;//记录数组candidates的长度public void backTravel(int[] candidates, int startIndex) { if(sum == T) {//如果组合总和等于目标值,将改组和放入结果集,然后返回result.add(new LinkedList<Integer>(path));return;}else if(sum > T) return;//由于数组中每个元素(2 <= candidates[i] <= 40),所以当总和大于目标值时,后面无论加多少个元素,总和一定大于target,所以之间返回。for(int i = startIndex; i < len; i++) {//从起始下标遍横向历数组path.add(candidates[i]);sum += candidates[i];backTravel(candidates, i);//递归path.pollLast();//回溯sum -= candidates[i];}}public List<List<Integer>> combinationSum(int[] candidates, int target) {T = target;sum = 0;len = candidates.length;backTravel(candidates, 0);return result;}
}
二、40. 组合总和 II
题目链接:40. 组合总和 II
题目描述:
给定一个候选人编号的集合 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] ]
提示:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
算法分析:
这道题的做法跟上一道题类似,不过要注意的时要对于重复的组合进行去重操作。
具体去重操作为:
首先回溯之前对数组进行排序,如此相同的元素会放在一起。
然后再横向遍历数组是,对同一个元素重复出现在同一个位置去重(注意同一个元素出现在不同位置时不去重)。
代码如下:
class Solution {List<List<Integer>>result = new ArrayList<>();//存放所有组合的结果集LinkedList<Integer> path = new LinkedList<>();//搜索每种组合int T;int sum;int len;public void backTravel(int[] candidates, int startIndex) {if(sum == T) {//如果总和等于目标值,将组合放入结果集返回result.add(new LinkedList<>(path));return;}else if(sum > T) return;//如果总和大于目标值,直接返回for(int i = startIndex; i < len; i++) {//从起始下标横向遍历数组if(i > startIndex && candidates[i] == candidates[i - 1]) continue;//一个元素重复出现在同一位置时,进行去重path.add(candidates[i]);sum += candidates[i];backTravel(candidates, i + 1);//递归path.removeLast();//回溯sum -= candidates[i];}}public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);T = target;sum = 0;len = candidates.length;backTravel(candidates, 0);return result;}
}
三、131. 分割回文串
题目链接:131. 分割回文串
题目描述:
给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1:
输入:s = "aab" 输出:[["a","a","b"],["aa","b"]]
示例 2:
输入:s = "a" 输出:[["a"]]
提示:
1 <= s.length <= 16s仅由小写英文字母组成
算法分析:
做法跟上两道题类似,也是用回溯算法不过在对每种方案添加元素(字符串时),要判断一下该子串是否是回文串。
所以我们还要在上面的基础上增加一个判断子串是否是回文串的方法。
具体待码如下:
class Solution {List<List<String>> result = new ArrayList<>();//用来存放每种方案的结果集LinkedList<String> path = new LinkedList<>();//用来遍历每种方案int len;//字符串的长度public boolean isPartition(String s, int left, int right) {//判断字串是否是回文串while(left <= right) {if(s.charAt(left) != s.charAt(right)) return false;left++;right--;}return true;}public void backTravel(String s, int startIndex) {if(startIndex == len) {//如果起始下标等于字符串的长度,说明有一个分割方案了,将方案放入结果集,然后返回result.add(new LinkedList<>(path));return;}else if(startIndex > len) return;//如果起始下标大于字符串长度,说明没有分割方案,直接返回。for(int i = startIndex; i < len; i++) {//遍历从起始下标到结尾的子串,并判断从起始下标到i的字串是否是回文串if(isPartition(s, startIndex, i) != true) continue;//如果不是回文串,继续下一层for循环。path.add(s.substring(startIndex, i + 1));backTravel(s, i + 1);//递归path.removeLast(); //回溯}}public List<List<String>> partition(String s) {len = s.length();backTravel(s, 0);return result;}
}
总结
回溯时,我们不要只会对整数数组回溯,还要会对各种数组进行回溯。
相关文章:
LeetCode算法题解(回溯)|39. 组合总和、40. 组合总和 II、131. 分割回文串
一、39. 组合总和 题目链接:39. 组合总和 题目描述: 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意…...
基于springboot实现招聘信息管理系统项目【项目源码+论文说明】
基于springboot实现招聘信息管理系统演示 摘要 在Internet高速发展的今天,我们生活的各个领域都涉及到计算机的应用,其中包括招聘信息管理系统的网络应用,在外国招聘信息管理系统已经是很普遍的方式,不过国内的线上管理系统可能还…...
Freeswitch实现软电话功能
1.话务步骤 分机注册->登录->拨打电话-> /*<--注册分机-->*/ EslMessage eslMessage1 inboundClient.sendApiCommand("callcenter_config agent set contact", "21009default user/1000"); System.out.println("#####dial eslMessa…...
RMI初探
接口 import java.rmi.Remote; import java.rmi.RemoteException;public interface IFoo extends Remote {String say(String name) throws RemoteException; }import java.rmi.Remote; import java.rmi.RemoteException;public interface IBar extends Remote {String buy(Str…...
NLP之BM25:BM25算法的简介、相关库、案例应用之详细攻略
NLP之BM25:BM25算法的简介、相关库、案例应用之详细攻略 目录 相关文章 NLP之BM25:BM25算法的简介、相关库、案例应用之详细攻略 Py之rank_bm25:rank_bm25的简介、安装、使用方法 BM25算法的简介...
YOLOv5改进,全维动态卷积
目录 一、理论部分 网络结构 实验结果 二、应用到YOLOv5 代码 yaml配置文件...
TypeScript学习Ts的类型声明,关于类
TypeScript是什么? 以JavaScript为基础构建的语言一个JavaScript的超集可以在任何支持JavaScript的平台上执行TypeScript扩展了JavaScript并添加了类型TS不能被JS解析器直接执行 TypeScript开发环境搭建 下载Node.js安装Node.js使用npm全局安装TypeScript&#x…...
Zabbix监控
一、zabbix 是什么? ●zabbix 是一个基于 Web 界面的提供分布式系统监视以及网络监视功能的企业级的开源解决方案。 ●zabbix 能监视各种网络参数,保证服务器系统的安全运营;并提供灵活的通知机制以让系统管理员快速定位/解决存在的各种问题…...
2023-11-04:用go语言,如果n = 1,打印 1*** 如果n = 2,打印 1*** 3*** 2*** 如果n = 3,打印
2023-11-04:用go语言,如果n 1,打印 1*** 如果n 2,打印 1***3*** 2*** 如果n 3,打印 1***3*** 2***4*** 5*** 6*** 如果n 4,打印 1***3*** 2***4*** 5*** 6***10** 9*** 8*** 7*** 输入…...
顺序表学习笔记(基础)
属于线性表旗下的一种,所以专门存储 one-to-one 关系的数据。 顺序表提供的具体实现方案是:将数据全部存储到一整块内存空间中,数据元素之间按照次序挨个存放。(类似数组) 顺序表中除了存储数据本身的值外࿰…...
PyTorch入门学习(十九):完整的模型验证套路
目录 一、图像加载和数据转换 二、模型加载 三、前向推理 四、结果解释 一、图像加载和数据转换 首先,需要加载待验证的图像,并将其转换为模型期望的输入大小和数据类型。以下是加载图像并进行数据转换的示例: import torch import tor…...
YOLO目标检测数据集大全【含voc(xml)、coco(json)和yolo(txt)三种格式标签+划分脚本+训练教程】(持续更新建议收藏)
一、作者介绍:资深图像算法工程师,YOLO算法专业玩家;擅长目标检测、语义分割、OCR等。 二、数据集介绍: 真实场景的高质量图片数据,数据场景丰富,分享的绝大部分数据集已应用于各种实际落地项目。所有数据…...
PHP保存时自动删除末尾的空格,phpstorm自动删除空白字符串
最近有个活儿,修改一个财务软件。 修改后给客户验收的过程中,客户反应有一个txt表格导出功能不能用了。之前是好的。 这次是新增,老的这个功能碰都没碰过,怎么能有问题呢?我心里OS 下班后我立马用系统导出TXT&#…...
2022 icpc杭州站 C. No Bug No Game - 背包dp
题面 分析 能拿整个 p i p_i pi的就拿整个的,不能拿了可以拿一部分的,因此可以分成0和1两种情况,0表示拿整个的,1表示还可以拿部分的,两种情况放在一起做一遍01背包,找到最大价值。 代码 #include &l…...
Temp directory ‘C:\WINDOWS\TEMP‘ does not exist
问题描述 解决方法 管理员权限问题,进入temp文件夹更改访问权限即可。 点击 temp文件夹 属性 -> 安全 -> 高级 -> 更改主体Users权限 给读取和写入权限 参考博客 开发springboot项目时无法启动Temp directory ‘C: \WINDOWS\TEMP‘ does not exist...
【单片机基础小知识-如何通过指针来读写寄存器】
寄存器的本质就是内存,RAM,而指针是可以对内存进行操作的,因此可以通过指针来读写寄存器。 如何读取以下一片地址: 步骤1、首地址 结构体,它所占用的内存空间大小与它内部成员有关。 构造一个28字节的类型 type…...
CountDownTimer倒计时使用
CountDownTimer倒计时使用 CountDownTimer使用 CountDownTimer 代码片. // An highlighted blockprivate MyCountDownTimer timer;private final long TIME 7 * 1000L;private final long INTERVAL 1000L;private class MyCountDownTimer extends CountDownTimer{/*** p…...
MySQL索引事务存储引擎
索引:是一个排序的列表 列表中存储的是索引的值和包含这个值数据所在行的物理地址 索引的作用 利用索引数据库可以快速定位 大大加快查询速度表的数据很大 或查询需要关联多个表 使用索引也可以查询速度加快表与表之间的连接速度使用分组和排序时可以大大减少时间提…...
【服务器使用】vscode winscp进行服务器容器连接(含修改初始密码)
1:获取docker的登陆信息 例如节点(host)、端口(port)、密码(passwd)等信息,这个自己找组内的前辈获取即可 2:配置config文件 找到vscode里面ssh处的config文件 人工找…...
Go和JavaScript结合使用:抓取网页中的图像链接
前言 在当今数字化时代,数据是金钱的源泉,对于许多项目和应用程序来说,获取并利用互联网上的数据是至关重要的。其中之一的需求场景是从网页中抓取图片链接,这在各种项目中都有广泛应用,特别是在动漫类图片收集项目中…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
R 语言科研绘图第 55 期 --- 网络图-聚类
在发表科研论文的过程中,科研绘图是必不可少的,一张好看的图形会是文章很大的加分项。 为了便于使用,本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中,获取方式: R 语言科研绘图模板 --- sciRplothttps://mp.…...
BLEU评分:机器翻译质量评估的黄金标准
BLEU评分:机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域,衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标,自2002年由IBM的Kishore Papineni等人提出以来,…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
渗透实战PortSwigger Labs指南:自定义标签XSS和SVG XSS利用
阻止除自定义标签之外的所有标签 先输入一些标签测试,说是全部标签都被禁了 除了自定义的 自定义<my-tag onmouseoveralert(xss)> <my-tag idx onfocusalert(document.cookie) tabindex1> onfocus 当元素获得焦点时(如通过点击或键盘导航&…...
比特币:固若金汤的数字堡垒与它的四道防线
第一道防线:机密信函——无法破解的哈希加密 将每一笔比特币交易比作一封在堡垒内部传递的机密信函。 解释“哈希”(Hashing)就是一种军事级的加密术(SHA-256),能将信函内容(交易细节…...
