代码随想录算法训练营第二十四天丨 回溯算法part02
216.组合总和III
思路
本题就是在 [1,2,3,4,5,6,7,8,9] 这个集合中找到和为n的k个数的组合。
相对于77. 组合 (opens new window),无非就是多了一个限制,本题是要找到和为n的k个数的组合,而整个集合已经是固定的了[1,...,9]。
本题k相当于树的深度,9(因为整个集合就是9个数)就是树的宽度。
例如 k = 2,n = 4的话,就是在集合[1,2,3,4,5,6,7,8,9]中求 k(个数) = 2, n(和) = 4的组合。
选取过程如图:
图中,可以看出,只有最后取到集合(1,3)和为4 符合条件。
回溯三部曲
- 确定递归函数参数
和77. 组合 (opens new window)一样,依然需要一维数组path来存放符合条件的结果,二维数组result来存放结果集。
这里我定义path 和 result为全局变量。
List<List<Integer>> res = new ArrayList<>(); // 存放结果集
LinkedList<Integer> path = new LinkedList<>(); // 符合条件的结果
接下来还需要如下参数:
- n(int)目标和,也就是题目中的n。
- k(int)就是题目中要求k个数的集合。
- sum(int)为已经收集的元素的总和,也就是path里元素的总和。
- startIndex(int)为下一层for循环搜索的起始位置。
所以代码如下:
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
void backtracking(int k, int n,int sum,int startIndex)
其实这里sum这个参数也可以省略,每次 n 减去选取的元素数值,然后判断如果targetSum为0了,说明收集到符合条件的结果了。
- 确定终止条件
什么时候终止呢?
k其实就已经限制树的深度,因为就取k个元素,树再往下深了没有意义。
所以如果path.size() 和 k相等了,就终止。
如果此时path里收集到的元素和(sum) 和n 相同了,就用result收集当前的结果。
所以 终止代码如下:
if (sum == n && k == path.size()){res.add(new ArrayList<>(path));return;
}
- 单层搜索过程
本题和77. 组合 (opens new window)区别之一就是集合固定的就是9个数[1,...,9],所以for循环固定i<=9
如图:
处理过程就是 path收集每次选取的元素,相当于树型结构里的边,sum来统计path里元素的总和。
代码如下:
// 上面剪枝 i <= 9 - (k - path.size()) + 1;
// 也可以改为 if (path.size() > k) return; 执行效率上是一样的
// 减枝 9 - (k - path.size()) + 1
for (int i = startIndex; i <= 9 - (k-path.size()) + 1; i++) {path.add(i);backtracking(k,n,sum+i,i+1);path.removeLast();
}
别忘了处理过程 和 回溯过程是一一对应的,处理有加,回溯就要有减!
剪枝
这道题目,剪枝操作其实是很容易想到.
已选元素总和如果已经大于n(图中数值为4)了,那么往后遍历就没有意义了,直接剪掉。
最终代码如下:
class Solution {public List<List<Integer>> combinationSum3(int k, int n) {backtracking(k,n,0,1);return res;}List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();void backtracking(int k, int n,int sum,int startIndex){// 减枝if (sum > n || path.size() > k){return;}if (sum == n && k == path.size()){res.add(new ArrayList<>(path));return;}// 上面剪枝 i <= 9 - (k - path.size()) + 1;// 也可以改为 if (path.size() > k) return; 执行效率上是一样的 // 减枝 9 - (k - path.size()) + 1for (int i = startIndex; i <= 9 - (k-path.size()) + 1; i++) {path.add(i);backtracking(k,n,sum+i,i+1);path.removeLast();}}
}
17.电话号码的字母组合
思路
从示例上来说,输入"23",最直接的想法就是两层for循环遍历了吧,正好把组合的情况都输出了。
如果输入"233"呢,那么就三层for循环,如果"2333"呢,就四层for循环.......
感觉和77.组合 (opens new window)遇到的一样的问题,就是这for循环的层数如何写出来,此时是用回溯法的时候了。
理解本题后,要解决如下三个问题:
- 数字和字母如何映射
- 两个字母就两个for循环,三个字符我就三个for循环,以此类推,然后发现代码根本写不出来
- 输入1 * #按键等等异常情况
#数字和字母如何映射
可以使用map或者定义一个二维数组,例如:string letterMap[10],来做映射,我这里定义一个二维数组,代码如下:
//定义一个二维数组,存放字母,初始对应所有的数字,为了直接对应2-9,新增了两个无效的字符串""
list.add(Arrays.asList(""));
list.add(Arrays.asList(""));
list.add(Arrays.asList("a","b","c"));
list.add(Arrays.asList("d","e","f"));
list.add(Arrays.asList("g","h","i"));
list.add(Arrays.asList("j","k","l"));
list.add(Arrays.asList("m","n","o"));
list.add(Arrays.asList("p","q","r","s"));
list.add(Arrays.asList("t","u","v"));
list.add(Arrays.asList("w","x","y","z"));
回溯法来解决n个for循环的问题
例如:输入:"23",抽象为树形结构,如图所示:
图中可以看出遍历的深度,就是输入"23"的长度,而叶子节点就是我们要收集的结果,输出["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。
回溯三部曲:
- 确定回溯函数参数
首先需要一个字符串s来收集叶子节点的结果,然后用一个字符串数组result保存起来,这两个变量定义为全局。
再来看参数,参数指定是有题目中给的string digits,然后还要有一个参数就是int型的startIndex。
这个startIndex是记录遍历第几个数字了,就是用来遍历 digits 的(题目中给出数字字符串),同时 startIndex 也表示树的深度。
代码如下:
//结果集
List<String> res = new ArrayList<>();
//每次迭代获取一个字符串,所以会设计大量的字符串拼接
StringBuilder sb = new StringBuilder();
void backtracking(String digits,int startIndex)
- 确定终止条件
例如输入用例"23",两个数字,那么根节点往下递归两层就可以了,叶子节点就是要收集的结果集。
那么终止条件就是如果startIndex 等于 输入的数字个数(digits.length() )了(本来index就是用来遍历digits的)。
然后收集结果,结束本层递归。
代码如下:
if (sb.length() == digits.length()){res.add(sb.toString());return;
}
- 确定单层遍历逻辑
首先要取startIndex指向的数字,并找到对应的字符集(手机键盘的字符集)。
然后for循环来处理这个字符集,代码如下:
for (int i = startIndex; i < digits.length(); i++) {//strs 表示当前num对应的字符串, 将startIndex指向的数字转为intList<String> strs = list.get(digits.charAt(i) - '0');//获得需要遍历的数组for (String str : strs) {sb.append(str);// 处理backtracking(digits, i + 1);// 递归,注意 i+1,一下层要处理下一个数字了sb.deleteCharAt(sb.length() - 1);// 回溯}
}
注意这里for循环,可不像是在回溯算法:求组合问题! (opens new window)和回溯算法:求组合总和! (opens new window)中从startIndex开始遍历的。
因为本题每一个数字代表的是不同集合,也就是求不同集合之间的组合,而77. 组合 (opens new window)和216.组合总和III (opens new window)都是求同一个集合中的组合!
注意:输入1 * #按键等等异常情况
代码中最好考虑这些异常情况,但题目的测试数据中应该没有异常情况的数据,所以我就没有加了。
但是要知道会有这些异常,如果是现场面试中,一定要考虑到!
代码如下:
class Solution {//结果集List<String> res = new ArrayList<>();//存放字母的List<List<String>> list = new ArrayList<>();//每次迭代获取一个字符串,所以会设计大量的字符串拼接StringBuilder sb = new StringBuilder();public List<String> letterCombinations(String digits) {//定义一个二维数组,存放字母,初始对应所有的数字,为了直接对应2-9,新增了两个无效的字符串""list.add(Arrays.asList(""));list.add(Arrays.asList(""));list.add(Arrays.asList("a","b","c"));list.add(Arrays.asList("d","e","f"));list.add(Arrays.asList("g","h","i"));list.add(Arrays.asList("j","k","l"));list.add(Arrays.asList("m","n","o"));list.add(Arrays.asList("p","q","r","s"));list.add(Arrays.asList("t","u","v"));list.add(Arrays.asList("w","x","y","z"));backtracking(digits,0);return res;}void backtracking(String digits,int startIndex){if (startIndex > digits.length() || digits.length() == 0){return;}if (sb.length() == digits.length()){res.add(sb.toString());return;}for (int i = startIndex; i < digits.length(); i++) {//strs 表示当前num对应的字符串, 将startIndex指向的数字转为intList<String> strs = list.get(digits.charAt(i) - '0');//获得需要遍历的数组for (String str : strs) {sb.append(str);// 处理backtracking(digits, i + 1);// 递归,注意 i+1,一下层要处理下一个数字了sb.deleteCharAt(sb.length() - 1);// 回溯}}}
}
以上为我做题时候的相关思路,自己的语言组织能力较弱,很多都是直接抄卡哥的,有错误望指正。
相关文章:

代码随想录算法训练营第二十四天丨 回溯算法part02
216.组合总和III 思路 本题就是在 [1,2,3,4,5,6,7,8,9] 这个集合中找到和为n的k个数的组合。 相对于77. 组合 (opens new window),无非就是多了一个限制,本题是要找到和为n的k个数的组合,而整个集合已经是固定的了[1,...,9]。 本题k相当于…...
【Python机器学习】零基础掌握AgglomerativeClustering聚类
如何解决城市规划问题? 城市规划者们面临一个复杂问题:如何合理地规划土地,使商业、居民、公园和其他设施互相便利,同时又不互相干扰?解决这个问题不仅需要对土地进行精准的分类,还要考虑到土地之间的相互关系。 借助层次聚类算法(Agglomerative Clustering),规划者…...

uniapp小程序中给web-view页面添加授权弹窗(使用cover-view组件覆盖实现该功能)
效果图: web-view是承载网页的容器。会自动铺满整个小程序页面,个人类型的小程序暂不支持使用。 再看下面一个提示: 每个页面只能有一个 web-view,web-view 会自动铺满整个页面,并覆盖其他组件。 也就是说,…...

2023年全球及中国CGT CDMO市场发展现状分析:CGT 渗透率有效助力CGT CDMO快速发展[图]
与传统药物相比,CGT的外包服务更注重活体开发过程,如质粒、病毒、细胞的生产及纯化。标准化、规模化的工艺流程对最终制备的产品起到重要影响,是获取及制备能够满足临床需求的高质量CGT产品的关键。 CGT CDMO服务内容 资料来源:共…...

上抖音热搜榜需要做哪些准备?
要想在抖音上获得高曝光,首先需要了解抖音热搜榜的算法和规则。抖音热搜榜的排名主要取决于作品的点赞数、评论数、分享数和播放量。其中,播放量是影响排名的关键因素。因此,在创作作品时,要注重提高作品的播放量。此外࿰…...
LDA代码训练报错记录
1、AttributeError: ‘CountVectorizer‘ object has no attribute ‘get_feature_names‘ 代码内容: tf_feature_names tf_vectorizer.get_feature_names()报错信息 AttributeError: CountVectorizer object has no attribute get_feature_names报错解析&#…...

【吞噬星空】爽翻,徐欣喜提永恒之体,罗峰秒杀败类,阿特金磕头认错
Hello,小伙伴们,我是小郑继续为大家深度解析国漫资讯。 吞噬星空动画第89集终于更新了,阿特金三大巨头的好日子到头了,从他们对徐欣出手的那一刻,就已经有取死之道。如今罗峰强势回归,上演复仇戏码,让大家看…...
【c++】跟webrtc学状态改变
peerconn的状态看起来只是为了通知上层PeerConnectionState // See https://w3c.github.io/webrtc-pc/#dom-rtcpeerconnectionstateenum class PeerConnectionState {kNew,kConnecting,kConnected,kDisconnected,kFailed,kClosed,};static constexpr absl...

【入门】.Net Core 6 WebApi 项目搭建
一、创建项目 1.1.创建新项目:打开开发工具>创建新项目>搜索API>选择C#语言的ASP.NET Core Web API 1.2.配置新项目:**自定义项目信息以及存储路径 1.3.其他信息:这里框架必须选择.NET 6.0,其他配置默认勾选即可,也可以根…...
xtrabackup备份 脚本
1、全量备份在周末晚上22点执行备份,增量是周一到周六晚上22点执行 2、考虑到增量备份第一次是根据全量备份开始备份,后面都是根据上一次增量备份在增量脚本做了if判断,周日做一次目录清理 3、每周日晚上91点50清理目录 22点就在次备份&#…...

13SpringMVC中拦截器的配置(拦截规则)和多个拦截器的preHandle,postHandle执行顺序原理详解
拦截器 Servlet中的过滤器的实现及其原理,参考文章 配置一个拦截器 SpringMVC中请求的处理流程: 用户请求—>listener—>filter—>DispatcherServlet—>filter—>preHandle—>controller—>postHandle 第一步: 编写一个Java类实现HandlerInterceptor(…...

Liunx中系统安全及文件系统(极其粗糙版)
PS:下面知识点还很粗糙下次有时间再改 系统安全: 系统安全和数据防护,数据备份的资质 比如三台服务器: 500万 工信部是有要求的,组织必须保证处理的个人数据的安全性 品牌形象如何维护呢 基于liunx的安全加固措施…...

Java中的数组
前言: 本篇博客将为大家介绍Java中的数组的相关知识。 目录 基本介绍 概念相关 数组的使用 数组是引用类型 应用场景 保存数据 作为方法的参数 作为方法的返回值 练习 数组转字符串 数组拷贝 求数组中元素的平均值 查找数组中的指定元素(二…...

Java反射调用jar包实现多态
上一篇实现了反射调用jar包,但是没有实现多态,这次先给自己的jar包类抽象一个接口,然后实现类实现接口。最后调用放反射得到的对像转换成接口类型调用执行。 定义接口,指定包为ZLZJar package ZLZJar;public interface ITest {p…...

PowerBI 一些基础功能
1、PowerBI创建日期表 1.1、Power BI 日期表 - 知乎日期是做数据分析的时候使用最频繁的分析维度,一般建议建立单独的日期维度表,并与事实表的日期字段建立连接。 建立日期维度表可通过DAX函数的方式进行: 日期表 CALENDAR(DATE("2023&…...
Mac用命令行安装Adobe代码字体Source Code Pro
执行命令 brew tap homebrew/cask-fonts && brew cask install font-source-code-pro...
RustDay05------Exercise[31-40]
31.结构体申明 结构体在这里给了三种声明样式 (1)字典样式的键值对(使用花括号) (2)元组样式的数值元组(使用圆括号) (3)空结构体,可以被格式化输出名字 // structs1.rs // Address all the TODOs to make the tests pass! // Execute rustlings hint structs1 or use the…...
wireshark过滤器的简单介绍
wireshark过滤器的简单介绍 Wireshark的过滤器主要分为捕获过滤器和显示过滤器两种,其中捕获过滤器在数据包捕获时起作用,而显示过滤器用于在已捕获的数据包的集合中筛选数据。以下是一些Wireshark过滤器的详细介绍: 捕获过滤器:…...

数据结构:二叉树(1)
目录 树的概念 树的表示形式 二叉树 二叉树的性质 题目 二叉树的存储 链式存储 初始化二叉树 二叉树的遍历 前序遍历:根👉左子树👉右子树 中序遍历:左子树👉根👉右子树 后序遍历:左子…...

[nlp] chathome—家居装修垂类大语言模型的开发和评估
ChatHome: Development and Evaluation of a Domain-Specific LanguageModel for Home Renovation ChatHome: 家居装修垂类大语言模型的开发和评估 1、摘要: 我们的方法包括两个步骤:首先,使用广泛的家庭装修数据集(包括专业文章、标准文档和网络内容)对通用模型进行后预训…...

黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...

微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
Python Einops库:深度学习中的张量操作革命
Einops(爱因斯坦操作库)就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库,用类似自然语言的表达式替代了晦涩的API调用,彻底改变了深度学习工程…...

leetcode73-矩阵置零
leetcode 73 思路 记录 0 元素的位置:遍历整个矩阵,找出所有值为 0 的元素,并将它们的坐标记录在数组zeroPosition中置零操作:遍历记录的所有 0 元素位置,将每个位置对应的行和列的所有元素置为 0 具体步骤 初始化…...
【java】【服务器】线程上下文丢失 是指什么
目录 ■前言 ■正文开始 线程上下文的核心组成部分 为什么会出现上下文丢失? 直观示例说明 为什么上下文如此重要? 解决上下文丢失的关键 总结 ■如果我想在servlet中使用线程,代码应该如何实现 推荐方案:使用 ManagedE…...