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

代码随想录 | Day28 | 回溯算法:组合组合总和III

代码随想录 | Day28 | 回溯算法:组合&&组合总和III

关于这个章节,大家最好是对递归函数的理解要比较到位,听着b站视频课可能呢才舒服点,可以先去搜一搜关于递归函数的讲解,理解,再开始这个章节会比较好一些

我觉得回溯就是对传入递归函数的参数加加减减,加了的减掉,减了的加上

主要学习内容:

组合题目的模板

77.组合

[77. 组合 - 力扣(LeetCode)](https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/)

解法思路:

首先,把问题转换为树形结构,树的每一层的各个结点都是由本层逻辑的for循环产生的,树的深度是由我们所求集合的大小决定的。

20201123195223940

我们在第一层取出一个数字,第一层就是 1 ,2 ,3 ,4

第二层从剩余的集合中取出一个数字,那就是 [1,2] [1,3] [1,4] …

而我们集合大小为2,那么就只有这两层,树的深度也就这两层

而我们选完[1,2]怎么返回[1]的时候去选择[1,3]呢?

这时候就是回溯算法,回溯就是恢复你选择之前的状态,让你去选择另外一个,本质上是穷举的思想

1.函数参数和返回值

vector<vector<int>> res; 
void backtracking(vector<int> path,int n,int k,int index)

res存放结果,path是当前已经收集的组合,n,k不必说,index表示我们已经选到哪个数字了,防止出现重复的组合

2.终止条件

我们当前收集的集合大小等于要求的大小就收集到最后的结果集中,然后返回,这也是能够控制树的深度只有两层的原因

if(path.size()==k)
{res.push_back(path);return;
}

3.本层代码逻辑

其实最难理解的就是for循环部分。

由于题目要求的是组合,我们只要防止重复,所以引入index,让index之前的已经选过的数不再出现,比如第一层选了2之后,index会让1和2不再出现,只会出现3,4,不会同时出现[1,2]和[2,1]这两个组合了

对for的理解可以脑补一下,举例比如选了1之后,本层的递归函数index是1

进入for循环,传入的先是2,在树的下一层,产生了[1,2]组合,大小满足2,结束递归返回上层,上层将2弹出,继续下一次循环,传入的就是3,产生了[1,3],以此类推

需要注意的是不要写成index+1,这个是错误的,会出现:在你选完第一层的数字后,不管你第一层选的数是多少,第二层都是从2开始的

错误案例

n=4,k=2

image-20241006172301826

最后递归函数返回来以后,把咱压入的元素再弹出就好

for(int i=index;i<=n;i++)
{path.push_back(i);backtracking(path,n,k,i+1);//注意不是index+1path.pop_back();//回溯,恢复现场
}

完整代码:

class Solution {
public:vector<vector<int>> res; void backtracking(vector<int> path,int n,int k,int index){if(path.size()==k){res.push_back(path);return;}for(int i=index;i<=n;i++){path.push_back(i);backtracking(path,n,k,i+1);//注意不是index+1path.pop_back();}}vector<vector<int>> combine(int n, int k) {vector<int> path;backtracking(path,n,k,1);return res;}
};

优化

注意代码中i,就是for循环里选择的起始位置,可以循环的次数少一点。(大家可以看代码随想录中的)

for (int i = startIndex; i <= n; i++) {

接下来看一下优化过程如下:

  1. 已经选择的元素个数:path.size();
  2. 所需需要的元素个数为: k - path.size();
  3. 列表中剩余元素(n-i) >= 所需需要的元素个数(k - path.size())
  4. 在集合n中至多要从该起始位置 : i <= n - (k - path.size()) + 1,开始遍历

为什么有个+1呢,因为包括起始位置,我们要是一个左闭的集合。

举个例子,n = 4,k = 3, 目前已经选取的元素为0(path.size为0),n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

从2开始搜索都是合理的,可以是组合[2, 3, 4]。

所以优化之后的for循环是:

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置

216.组合总和III

216. 组合总和 III - 力扣(LeetCode)

思路:

思路和上一题一模一样,就是上一题给定的n换成了9,然后多了一个加和的操作

加和的操作你可以等到有3个数以后再加起来进行比较,也可以在递归的过程中累加并且比较

1.函数返回值和参数

vector<vector<int>> res;
void backtracking(vector<int> path,int k,int sum,int n,int index)

res记录结果

path收集当前组合

k组合大小

n总和值

sum当前集合的总和

index从哪个数开始

2.终止条件

当前总和已经大于n了,没必要再递归了

如果大小等于k并且加起来等于n,收集结果,不等于n直接返回

if(sum>n)return ;
if(path.size()==k)
{if(sum==n)res.push_back(path);return;
}

3.本层逻辑

优化的思路一样的直接套用了

和上一题不一样的就是多加了一个总和值sum

让sum加上我们压入path的值i传入下层即可,下层函数会在终止条件进行比较。

for(int i=index;i<=9-(k-path.size())+1;i++)
{path.push_back(i);backtracking(path,k,sum+i,n,i+1);//也可以写成 递归函数前写sum+=i,递归函数后写sum-=i,也可以写在递归函数参数中,比如我这样的path.pop_back();//回溯过程
}

完整代码:

class Solution {
public:vector<vector<int>> res;void backtracking(vector<int> path,int k,int sum,int n,int index){if(sum>n)return ;if(path.size()==k){if(sum==n)res.push_back(path);return;}for(int i=index;i<=9-(k-path.size())+1;i++){path.push_back(i);backtracking(path,k,sum+i,n,i+1);path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {vector<int> path;backtracking(path,k,0,n,1);return res;}
};

相关文章:

代码随想录 | Day28 | 回溯算法:组合组合总和III

代码随想录 | Day28 | 回溯算法&#xff1a;组合&&组合总和III 关于这个章节&#xff0c;大家最好是对递归函数的理解要比较到位&#xff0c;听着b站视频课可能呢才舒服点&#xff0c;可以先去搜一搜关于递归函数的讲解&#xff0c;理解&#xff0c;再开始这个章节会比…...

【重学 MySQL】四十五、数据库的创建、修改与删除

【重学 MySQL】四十五、数据库的创建、修改与删除 一条数据存储的过程数据输入数据验证数据处理数据存储数据持久化反馈与日志注意事项 标识符命名规则基本规则长度限制保留字与特殊字符命名建议示例 MySQL 中的数据类型创建数据库创建数据库时指定字符集和排序规则 查看数据库…...

STM32驱动直流电机

stm32通过PWM控制直流电机的方向和速度。 小直流电机需要几百毫安的电流&#xff0c;单片机只能提供几毫安的电流。电机内线圈转动时切割磁感线以及电机内转子线圈的电感效应都会产生反电动势&#xff0c;损坏芯片。 电机驱动芯片能够作为STM32驱动电机的帮手。 SLEEP暂停工作…...

【C++】二叉搜索树+变身 = AVL树

&#x1f680;个人主页&#xff1a;小羊 &#x1f680;所属专栏&#xff1a;C 很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~ 目录 前言一、AVL树二、AVL树的实现2.1 平衡因子2.2 旋转处理2.2.1 左单旋&#xff1a;插入新节点后单纯的右边高2.2.2 …...

Flutter String 按 ,。分割

在 Flutter 中&#xff0c;如果你想将一个字符串按特定的字符&#xff08;例如中文逗号 &#xff0c; 和英文句号 .&#xff09;进行分割&#xff0c;可以使用 Dart 语言的字符串处理功能。具体来说&#xff0c;你可以使用 split 方法&#xff0c;并传入一个正则表达式来匹配这…...

Redis: 集群高可用之MOVED转向和ASK转向解决方案

MOVED转向 1 ) 问题描述 在客户端操作Redis集群的时候 MOVED转向 或 MOVED错误是经常遇到的一类问题我们先连入集群&#xff1a;$ /usr/local/redis/bin/redis-cli -a 123456 -h 192.168.10.101 -p 6371之前在Redis中存储过一些数据&#xff0c;比如下面的情况&#xff0c;当输…...

idea插件市场安装没反应

https://plugins.jetbrains.com/idea重启后还是不行那就...

数据结构之排序(5)

摘要&#xff1a;本文主要讲各种排序算法&#xff0c;注意它们的时间复杂度 概念 将各元素按关键字递增或递减排序顺序重新排列 评价指标 稳定性: 关键字相同的元素经过排序后相对顺序是否会改变 时间复杂度、空间复杂度 分类 内部排序——数据都在内存中 外部排序——…...

R包的安装、加载以及如何查看帮助文档

0x01 如何安装R包 一、通过R 内置函数安装&#xff08;常用&#xff09; 1.安装CRAN的R包 install.packages()是一个用于安装 R 包的重要函数。 语法&#xff1a;install.packages(pkgs, repos getOption("repos"),...) 其中&#xff1a; pkgs&#xff1a;要安…...

【YOLO学习】YOLOv3详解

文章目录 1. 网络结构1.1 结构介绍1.2 改进 2. 训练与测试过程3. 总结 1. 网络结构 1.1 结构介绍 1. 与 YOLOv2 不同的是&#xff0c;YOLOv3 在 Darknet-19 里加入了 ResNet 残差连接&#xff0c;改进之后的模型叫 Darknet-53。在 ImageNet上 实验发现 Darknet-53 相对于 ResN…...

JDK1.0主要特性

JDK 1.0&#xff0c;也被称为Java 1&#xff0c;是Java编程语言的第一个正式版本&#xff0c;由Sun Microsystems公司在1996年发布。JDK 1.0的发布标志着Java作为一种编程语言和平台的正式诞生&#xff0c;它带来了许多创新的概念和特性&#xff0c;对后来的软件开发产生了深远…...

CSS基础-盒子模型(三)

9、CSS盒子模型 9.1 CSS常用长度单位 1、px&#xff1a;像素&#xff1b; 2、em&#xff1a;相对元素font-size的倍数&#xff1b; 3、rem&#xff1a;相对根字体的大小&#xff0c;html标签即是根&#xff1b; 4、%&#xff1a;相对于父元素进行计算。 注意&#xff1a;CSS样…...

深度学习中的损失函数详解

深度学习中的损失函数详解 文章目录 深度学习中的损失函数详解损失函数的基础概念常见的损失函数类型及应用场景回归问题的损失函数分类问题的损失函数自定义损失函数 如何选择合适的损失函数&#xff1f;损失函数在深度学习中的应用 在深度学习的世界中&#xff0c;损失函数&a…...

系统架构设计师-下午案例题(2022年下半年)

1.试题-(共25分):阅读以下关于软件架构设计与评估的叙述在答题纸上回答问题1和问题2。 【说明】某电子商务公司拟升级其会员与促销管理系统&#xff0c;向用户提供个性化服务&#xff0c;提高用户的粘性。在项目立项之初&#xff0c;公司领导层一致认为本次升级的主要目标是提…...

高级图片编辑器Photopea

什么是 Photopea &#xff1f; Photopea 是一款免费的在线工具&#xff0c;用于编辑光栅和矢量图形&#xff0c;支持PSD、AI 和 Sketch文件。 功能上&#xff0c;Photopea 和 老苏之前介绍的 miniPaint 比较像 文章传送门&#xff1a;在线图片编辑器miniPaint 支持的格式 复杂…...

详解zookeeper四字命令

ZooKeeper 的四字命令&#xff08;Four-Letter Words, 4LW&#xff09;是一组简单的管理和监控命令&#xff0c;方便运维人员快速获取 ZooKeeper 集群和节点的运行状态。这些命令通常用于健康检查、性能监控、节点配置查看等操作。通过这些命令&#xff0c;可以轻松获取关于 Zo…...

docker 进入容器运行命令

要进入正在运行的Docker容器并在其中执行命令&#xff0c;你可以使用docker exec命令。以下是具体步骤和示例&#xff1a; 1. 查看正在运行的容器 首先&#xff0c;确认你的容器正在运行&#xff0c;可以使用以下命令查看所有运行中的容器&#xff1a; docker ps2. 进入容器…...

一行 Python 代码能实现什么丧心病狂的功能?圣诞树源代码

手头有 109 张头部 CT 的断层扫描图片&#xff0c;我打算用这些图片尝试头部的三维重建。基础工作之一&#xff0c;就是要把这些图片数据读出来&#xff0c;组织成一个三维的数据结构&#xff08;实际上是四维的&#xff0c;因为每个像素有 RGBA 四个通道&#xff09;。 这个…...

mit6824-01-MapReduce详解

文章目录 MapReduce简述编程模型执行流程执行流程排序保证Combiner函数Master数据结构 容错性Worker故障Master故障 性能提升定制分区函数局部性执行缓慢的worker(slow workers) 常见问题总结回顾参考链接 MapReduce简述 MapReduce是一个在多台机器上并行计算大规模数据的软件架…...

在Docker中运行微服务注册中心Eureka

1、Docker简介&#xff1a; 作为开发者&#xff0c;经常遇到一个头大的问题&#xff1a;“在我机器上能运行”。而将SpringCloud微服务运行在Docker容器中&#xff0c;避免了因环境差异带来的兼容性问题&#xff0c;能够有效的解决此类问题。 通过Docker&#xff0c;开发者可…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...