当前位置: 首页 > 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、摘要: 我们的方法包括两个步骤:首先,使用广泛的家庭装修数据集(包括专业文章、标准文档和网络内容)对通用模型进行后预训…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...