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结合使用:抓取网页中的图像链接
前言 在当今数字化时代,数据是金钱的源泉,对于许多项目和应用程序来说,获取并利用互联网上的数据是至关重要的。其中之一的需求场景是从网页中抓取图片链接,这在各种项目中都有广泛应用,特别是在动漫类图片收集项目中…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
R 语言科研绘图第 55 期 --- 网络图-聚类
在发表科研论文的过程中,科研绘图是必不可少的,一张好看的图形会是文章很大的加分项。 为了便于使用,本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中,获取方式: R 语言科研绘图模板 --- sciRplothttps://mp.…...
基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
安卓基础(Java 和 Gradle 版本)
1. 设置项目的 JDK 版本 方法1:通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分,设置 Gradle JDK 方法2:通过 Settings File → Settings... (或 CtrlAltS)…...
自然语言处理——文本分类
文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益(IG) 分类器设计贝叶斯理论:线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别, 有单标签多类别文本分类和多…...
