当前位置: 首页 > news >正文

代码随想录算法训练营第二十四天丨 回溯算法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

如图: 

216.组合总和III

处理过程就是 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循环的层数如何写出来,此时是用回溯法的时候了。

理解本题后,要解决如下三个问题:

  1. 数字和字母如何映射
  2. 两个字母就两个for循环,三个字符我就三个for循环,以此类推,然后发现代码根本写不出来
  3. 输入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",抽象为树形结构,如图所示:

17. 电话号码的字母组合

图中可以看出遍历的深度,就是输入"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)&#xff0c;无非就是多了一个限制&#xff0c;本题是要找到和为n的k个数的组合&#xff0c;而整个集合已经是固定的了[1,...,9]。 本题k相当于…...

【Python机器学习】零基础掌握AgglomerativeClustering聚类

如何解决城市规划问题? 城市规划者们面临一个复杂问题:如何合理地规划土地,使商业、居民、公园和其他设施互相便利,同时又不互相干扰?解决这个问题不仅需要对土地进行精准的分类,还要考虑到土地之间的相互关系。 借助层次聚类算法(Agglomerative Clustering),规划者…...

uniapp小程序中给web-view页面添加授权弹窗(使用cover-view组件覆盖实现该功能)

效果图&#xff1a; web-view是承载网页的容器。会自动铺满整个小程序页面&#xff0c;个人类型的小程序暂不支持使用。 再看下面一个提示&#xff1a; 每个页面只能有一个 web-view&#xff0c;web-view 会自动铺满整个页面&#xff0c;并覆盖其他组件。 也就是说&#xff0c;…...

2023年全球及中国CGT CDMO市场发展现状分析:CGT 渗透率有效助力CGT CDMO快速发展[图]

与传统药物相比&#xff0c;CGT的外包服务更注重活体开发过程&#xff0c;如质粒、病毒、细胞的生产及纯化。标准化、规模化的工艺流程对最终制备的产品起到重要影响&#xff0c;是获取及制备能够满足临床需求的高质量CGT产品的关键。 CGT CDMO服务内容 资料来源&#xff1a;共…...

上抖音热搜榜需要做哪些准备?

要想在抖音上获得高曝光&#xff0c;首先需要了解抖音热搜榜的算法和规则。抖音热搜榜的排名主要取决于作品的点赞数、评论数、分享数和播放量。其中&#xff0c;播放量是影响排名的关键因素。因此&#xff0c;在创作作品时&#xff0c;要注重提高作品的播放量。此外&#xff0…...

LDA代码训练报错记录

1、AttributeError: ‘CountVectorizer‘ object has no attribute ‘get_feature_names‘ 代码内容&#xff1a; tf_feature_names tf_vectorizer.get_feature_names()报错信息 AttributeError: CountVectorizer object has no attribute get_feature_names报错解析&#…...

【吞噬星空】爽翻,徐欣喜提永恒之体,罗峰秒杀败类,阿特金磕头认错

Hello,小伙伴们&#xff0c;我是小郑继续为大家深度解析国漫资讯。 吞噬星空动画第89集终于更新了&#xff0c;阿特金三大巨头的好日子到头了&#xff0c;从他们对徐欣出手的那一刻&#xff0c;就已经有取死之道。如今罗峰强势回归&#xff0c;上演复仇戏码&#xff0c;让大家看…...

【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.创建新项目&#xff1a;打开开发工具>创建新项目>搜索API>选择C#语言的ASP.NET Core Web API 1.2.配置新项目&#xff1a;**自定义项目信息以及存储路径 1.3.其他信息&#xff1a;这里框架必须选择.NET 6.0,其他配置默认勾选即可&#xff0c;也可以根…...

xtrabackup备份 脚本

1、全量备份在周末晚上22点执行备份&#xff0c;增量是周一到周六晚上22点执行 2、考虑到增量备份第一次是根据全量备份开始备份&#xff0c;后面都是根据上一次增量备份在增量脚本做了if判断&#xff0c;周日做一次目录清理 3、每周日晚上91点50清理目录 22点就在次备份&#…...

13SpringMVC中拦截器的配置(拦截规则)和多个拦截器的preHandle,postHandle执行顺序原理详解

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

Liunx中系统安全及文件系统(极其粗糙版)

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

Java中的数组

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

Java反射调用jar包实现多态

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

PowerBI 一些基础功能

1、PowerBI创建日期表 1.1、Power BI 日期表 - 知乎日期是做数据分析的时候使用最频繁的分析维度&#xff0c;一般建议建立单独的日期维度表&#xff0c;并与事实表的日期字段建立连接。 建立日期维度表可通过DAX函数的方式进行&#xff1a; 日期表 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的过滤器主要分为捕获过滤器和显示过滤器两种&#xff0c;其中捕获过滤器在数据包捕获时起作用&#xff0c;而显示过滤器用于在已捕获的数据包的集合中筛选数据。以下是一些Wireshark过滤器的详细介绍&#xff1a; 捕获过滤器&#xff1a;…...

数据结构:二叉树(1)

目录 树的概念 树的表示形式 二叉树 二叉树的性质 题目 二叉树的存储 链式存储 初始化二叉树 二叉树的遍历 前序遍历&#xff1a;根&#x1f449;左子树&#x1f449;右子树 中序遍历&#xff1a;左子树&#x1f449;根&#x1f449;右子树 后序遍历&#xff1a;左子…...

[nlp] chathome—家居装修垂类大语言模型的开发和评估

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

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

leetcode73-矩阵置零

leetcode 73 思路 记录 0 元素的位置&#xff1a;遍历整个矩阵&#xff0c;找出所有值为 0 的元素&#xff0c;并将它们的坐标记录在数组zeroPosition中置零操作&#xff1a;遍历记录的所有 0 元素位置&#xff0c;将每个位置对应的行和列的所有元素置为 0 具体步骤 初始化…...

【java】【服务器】线程上下文丢失 是指什么

目录 ■前言 ■正文开始 线程上下文的核心组成部分 为什么会出现上下文丢失&#xff1f; 直观示例说明 为什么上下文如此重要&#xff1f; 解决上下文丢失的关键 总结 ■如果我想在servlet中使用线程&#xff0c;代码应该如何实现 推荐方案&#xff1a;使用 ManagedE…...