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

news/2024/2/27 22:59:15

39. 组合总和

题目链接:39. 组合总和

与组合问题类似,关键是理解startIndex的作用,它是控制每组内部,每个元素的选择,如果传入的是i,则组内可重复并且组间不重复,为什么?因为外部有for循环会控制i一直自增前进,然后还有回溯操作,之前被选过的数字在回溯之后是不会再被选择了。下面是没有剪枝之后的代码。

代码1.0:

class Solution {// 1. 不剪枝版本,2ms通过List<Integer> temp = new ArrayList<>();List<List<Integer>> result  = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {backtracking(candidates, target, 0);return result;}public void backtracking(int[] candidates, int target, int startIndex) { if(target < 0) {                      // 必须放在外面,因为小于零而退出的,通过回溯来让数据恢复return;}          if(target == 0) {result.add(new ArrayList<>(temp));return;}for(int i = startIndex; i < candidates.length; i++) {target -= candidates[i];temp.add(candidates[i]);    backtracking(candidates,target, i);// 起始位置传入i,确保数字可以重复选,但是每组不重复 temp.remove(temp.size() - 1);// 回溯,把导致target小于零的数去掉target += candidates[i];}}
}

剪枝其实直接放在每次的for循环中,如果目标值减去下一个值已经不满足条件(小于0),则直接跳过下面这个值。而这样,也就少了一个终止条件了,下面是剪枝之后的代码。

代码2.0(剪枝版本):

class Solution {// 2. 剪枝之后的版本,1ms通过List<Integer> temp = new ArrayList<>();List<List<Integer>> result  = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {backtracking(candidates, target, 0);return result;}public void backtracking(int[] candidates, int target, int startIndex) {if(target == 0) {result.add(new ArrayList<>(temp));return;}for(int i = startIndex; i < candidates.length; i++) {if(target - candidates[i] < 0) {    // 如果减的这个已经小于0,那就没必要加入集合了,直接遍历集合的下一个元素continue;}target -= candidates[i];temp.add(candidates[i]);    // 要加入之后再判断,因为不符合的部分会在回溯部分删除掉backtracking(candidates,target, i);temp.remove(temp.size() - 1);target += candidates[i];}}
}

40.组合总和II

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

这题又涉及一个经典问题:“去重”,这里我还是更偏向于先排序之后的去重操作,我自认为更好理。首先这道题是组内不可重复,所以递归时要传i + 1给startIndex,而何时去重呢?排序之后相同元素都在一起,当找到一个满足条件的组合之后,在回溯的地方判断去重:即,满足条件的下一个元素是否和当前满足条件的最后一个元素相同,如果是,则跳过(用一个while循环)。

代码:

class Solution {List<Integer> temp = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);// 先排序,把相同的元素放在一起,方便去重backtracking(candidates, target, 0);return result;}public void backtracking(int[] candidates, int target, int startIndex) {if(target == 0) {result.add(new ArrayList<>(temp));return;}for(int i = startIndex; i < candidates.length; i++) {if(target - candidates[i] < 0) {    // 剪枝,有了这一步,在外面的循环就可以少一个退出条件了,因为达到退出条件的,只有符合条件的结果集了continue;}target -= candidates[i];temp.add(candidates[i]);backtracking(candidates, target, i + 1);target += candidates[i];temp.remove(temp.size() - 1);// 回溯之后,为了保证下一次取的数字不重复,一直移动i,便能确保去重,注意要先控制i + 1小于数组大小,否则会出现空指针异常while(i + 1< candidates.length && candidates[i + 1] ==candidates[i]) {i++;}}}
}

131.分割回文串

这道题的关键在于怎么切割。而对于Java,切割的方式还是挺多的,下面一一介绍。

1. 用String类存储每一次新的子穿开头,用+来拼接

代码1.0:

class Solution {List<String> temp = new ArrayList<>();List<List<String>> result = new ArrayList<>();public List<List<String>> partition(String s) {backtracking(s, 0);return result;}private void backtracking(String s, int startIndex) {if(startIndex > s.length() - 1) {result.add(new ArrayList<>(temp));return;}String str = "";for(int i = startIndex; i < s.length(); i++) {// System.out.println(str + s.charAt(i));str += s.charAt(i);if(!isHui(str)) {continue;}temp.add(str);// System.out.println(temp.toString());backtracking(s, i + 1);temp.remove(temp.size() - 1);}}public boolean isHui(String s) {int left = 0;int right = s.length() - 1;while(left < right) {if(s.charAt(left) != s.charAt(right)) {return false;}left++;right--;}return true;}
}

用时最慢,需要17ms

2. 用StringBuilder类自带方法来处理拼接操作

代码2.0:

class Solution {// 2.0 用StringBuilder类的拼接方法比用加法拼接更高效List<String> temp = new ArrayList<>();List<List<String>> result = new ArrayList<>();public List<List<String>> partition(String s) {backtracking(s, 0);return result;}private void backtracking(String s, int startIndex) {if(startIndex > s.length() - 1) { // 传入的起始下标超过字符串最后一个元素时,说明切割结束,可以返回结果了result.add(new ArrayList<>(temp));return;}StringBuilder str = new StringBuilder(); // 每次循环都定义一个新的容器来获取切割的字符串for(int i = startIndex; i < s.length(); i++) {str.append(s.charAt(i));      // 用字符串拼接来获取后面的子串if(!isHui(str.toString())) {  // 不是回文的字符串就不加入到temp中,等待下一次拼接,成为回文穿之后再加入continue;}temp.add(str.toString());backtracking(s, i + 1);       // 切割的本质其实是for循环中i的移动,与递归调用i + 1(调用i+1还有个作用是防止组间重复的出现)temp.remove(temp.size() - 1);}}public boolean isHui(String s) {int left = 0;int right = s.length() - 1;while(left < right) {if(s.charAt(left) != s.charAt(right)) {return false;}left++;right--;}return true;}
}

这个速度也只是快在拼接上,但是由于判断是回文串时,要转化为String类型,所以还是没有达到最快,用时11ms

3. 用String类自带切割方法

代码3.0:

class Solution {List<String> temp = new ArrayList<>();List<List<String>> result = new ArrayList<>();public List<List<String>> partition(String s) {backtracking(s, 0);return result;}private void backtracking(String s, int startIndex) {if(startIndex > s.length() - 1) {result.add(new ArrayList<>(temp));return;}String str = "";for(int i = startIndex; i < s.length(); i++) {str = s.substring(startIndex, i + 1);if(!isHui(str)) {continue;}temp.add(str);backtracking(s, i + 1);temp.remove(temp.size() - 1);}}public boolean isHui(String s) {int left = 0;int right = s.length() - 1;while(left < right) {if(s.charAt(left) != s.charAt(right)) {return false;}left++;right--;}return true;}
}

直接是String类自带方法,用时最快:8ms!


http://www.ppmy.cn/news/1350512.html

相关文章

2024年华为OD机试真题-攀登者1-Python-OD统一考试(C卷)

题目描述: 攀登者喜欢寻找各种地图,并且尝试攀登到最高的山峰。 地图表示为一维数组,数组的索引代表水平位置,数组的高度代表相对海拔高度。其中数组元素0代表地面。 例如[0,1,2,4,3,1,0,0,1,2,3,1,2,1,0], 代表如下图所示的地图,地图中有两个山脉位置分别为 1,2,3,4,5和8…

HarmonyOS 状态管理装饰器 Observed与ObjectLink 处理嵌套对象/对象数组 结构双向绑定

本文 我们还是来说 两个 harmonyos 状态管理的装饰器 Observed与ObjectLink 他们是用于 嵌套对象 或者 以对象类型为数组元素 的数据结构 做双向同步的 之前 我们说过的 state和link 都无法捕捉到 这两种数据内部结构的变化 这里 我们模拟一个类数据结构 class Person{name:…

React18原理: 渲染与更新时的重点关注事项

概述 react 在渲染过程中要做很多事情&#xff0c;所以不可能直接通过初始元素直接渲染还需要一个东西&#xff0c;就是虚拟节点&#xff0c;暂不涉及React Fiber的概念&#xff0c;将vDom树和Fiber 树统称为虚拟节点有了初始元素后&#xff0c;React 就会根据初始元素和其他可…

【自然语言处理】:实验1布置,Word2VecTranE的实现

清华大学驭风计划 因为篇幅原因实验答案分开上传&#xff0c;后续持续更新中&#xff0c;请敬请期待 如果需要详细的实验报告或者代码可以私聊博主 有任何疑问或者问题&#xff0c;也欢迎私信博主&#xff0c;大家可以相互讨论交流哟~~ 实验1&#xff1a; Word2Vec&Tra…

linux下ipconfig命令报:command not found 解决方法

参考博文&#xff1a; linux下ipconfig命令报:command not found 解决方法 CentOS7更新yum报Could not resolve host:mirrorlist.centos.org; Unknown error解决办法

SpringCloud-项目引入Nacos

一、安装Nacos服务 首先&#xff0c;我们需要从 Nacos 的官方网站下载发布版本。下载地址&#xff1a;Releases alibaba/nacos GitHub 选择合适的版本并下载&#xff0c;解压缩得到 Nacos 的安装包。 在解压后的 Nacos 目录中&#xff0c;找到 bin 文件夹。 用写字板编辑…

【Ubuntu 20.04/22.04 LTS】最新 esp-matter SDK 软件编译环境搭建步骤

仓库链接&#xff1a;esp-matter SDK官方软件说明&#xff1a;ESP Matter Programming Guide官方参考文档&#xff1a;使用 Matter-SDK 快速搭建 Matter 环境 (Linux) 环境要求 Ubuntu 20.04 或 Ubuntu22.04网络环境支持访问 Gihub 在安装 esp-matter SDK 软件编译环境之前&a…

梯度提升树系列7——深入理解GBDT的参数调优

目录 写在开头1. GBDT的关键参数解析1.1 学习率(learning rate)1.2 树的数量(n_estimators)1.3 树的最大深度(max_depth)1.4 叶子节点的最小样本数(min_samples_leaf)1.5 特征选择的比例(max_features)1.6 最小分裂所需的样本数(min_samples_split)1.7 子采样比例(…

【数据结构】14 队列(带头结点的链式存储和顺序存储实现)

定义 队列是一个有序线性表&#xff0c;但是队列的插入、删除操作是分别在线性表的两个不同端点进行的。 设一个队列 Q ( a 1 , a 2 , . . . , a n ) Q (a_1, a_2,...,a_n) Q(a1​,a2​,...,an​)&#xff0c;那么 a 1 a_1 a1​被称为队头元素&#xff0c; a n a_n an​为队…

「Linux」基础命令

目录结构 Linux只有1个顶级目录&#xff0c;称为“根目录”路径之间的层级关系&#xff0c;使用/来表示&#xff0c;例如&#xff1a;/usr/local/hello.txt 开头的/表示根目录后面的/表示层级关系 命令入门 命令的通用格式&#xff1a;command [ -options ] [ parameter] c…

软件架构与系统架构:区别与联系的分析

软件架构与系统架构&#xff1a;区别与联系的分析 在信息技术领域&#xff0c;软件架构和系统架构这两个术语经常被提及。尽管它们在某些方面有重叠&#xff0c;但它们确实代表了不同的概念和聚焦点。理解这两种架构之间的区别和联系对于任何从事技术开发和设计的专业人士都是至…

PMP-情景模拟学习法-识别项目阶段

《指南》和题目中采用了一种默认划分方法&#xff0c;把项目分为&#xff1a;启动、规划、执行和收尾这四个通用阶段。PMP考试和每个问题几乎都是基于特定阶段的情况提出的。 第一&#xff0c;启动阶段&#xff1a;项目章程正式批准之前的时间&#xff0c;可以统称为启动阶段&a…

已解决org.springframework.web.HttpMediaTypeNotSupportedException异常的正确解决方法,亲测有效!!!

已解决org.springframework.web.HttpMediaTypeNotSupportedException异常的正确解决方法&#xff0c;亲测有效&#xff01;&#xff01;&#xff01; 文章目录 问题分析 报错原因 解决思路 解决方法 总结 问题分析 在开发基于Spring框架的Web应用时&#xff0c;我们可能…

【JavaScrpt 漫游】【015】JSON 对象简记

文章简介 本文为【JavaScript 漫游】专栏的第 015 篇文章&#xff0c;主要是对 JS 语言中的 JSON 对象的知识点进行了简要记录。 JSON 格式JSON 对象JSON.stringify()JSON.parse() JSON 格式 JSON 格式&#xff08;JavaScript Object Notation 的缩写&#xff09;是一种用于…

第十二周学习报告

比赛 参加了一场 div 2 &#xff0c;B 题&#xff0c;C 题没写出来&#xff0c;B 是一个排序去重&#xff0b;双指针&#xff0c;C题是要观察出一个数学结论&#xff08;因为数据范围太大&#xff0c;我暴力做直接超时了&#xff09; 排 6253 &#xff0c;表现分是 998 &…

[JavaWeb玩耍日记]Maven的安装与使用

目录 一.作用 二.安装 三.使用 2.对项目使用compile命令进行编译,看看新的文件会在哪里产生&#xff1f; 3.需要认识的命令 4.Maven对项目执行不同命令的生命周期特点&#xff1f; 5.如何导入工程外的Maven&#xff1f; 6.如何直观地查看Maven导入了哪些工程或哪些jar包…

LeetCode:67.二进制求和

67. 二进制求和 - 力扣&#xff08;LeetCode&#xff09; 又是一道求和题&#xff0c;% / 在求和的用途了解了些&#xff0c; 目录 题目&#xff1a; 思路分析&#xff1a; 博主代码: 官方代码&#xff1a; 每日表情包&#xff1a; 题目&#xff1a; 思路分析&#xf…

Linux操作系统基础(七):Linux常见命令(二)

文章目录 Linux常见命令&#xff08;二&#xff09; 一、kill命令 二、ifconfig命令 三、clear命令 四、重启与关机命令 五、which命令 六、hostname命令 七、grep命令 八、|管道 九、useradd命令 十、userdel命令 十一、tar命令 十二、su命令 十三、ps命令 Linu…

lv15 驱动高级设备模型 1

之前的驱动操作称为硬编 一、起源 仅devfs&#xff08;dev目录&#xff09;&#xff0c;导致开发不方便以及一些功能难以支持&#xff1a; 热插拔&#xff08;如何插入一个设备然后找到设备的驱动应用到程序中&#xff09; 不支持一些针对所有设备的统一操作&#xff08;如电…

网络安全漏洞管理十大度量指标

当前&#xff0c;网络安全漏洞所带来的风险及产生的后果&#xff0c;影响到网络空间乃至现实世界的方方面面&#xff0c;通信、金融、能源、电力、铁路、医院、水务、航空、制造业等行业各类勒索、数据泄露、供应链、钓鱼等网络安全攻击事件层出不穷。因此&#xff0c;加强对漏…
最新文章