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

面试热点题:回溯算法之组合 组合与组合总和 III

什么是回溯算法?

回溯算法也可以叫回溯搜索算法,回溯是递归的"副产品",回溯的本质是穷举,然后选出我们需要的数据,回溯本身不是特别高效的算法,但我们可以通过"剪枝"来优化它。

理解回溯算法

回溯算法的解决可以模拟成树的结构,因为回溯法解决的是在集合中递归搜索子集的过程,集合的大小构成树的宽度,递归的深度构成树的深度

回溯算法模板

  1. 确定回溯算法的返回值与参数(一般先写逻辑,然后需要什么参数,就增加什么参数)
  2. 确定回溯函数的终止条件
  3. 确定回溯搜查的遍历过程
void BackTracking(参数)
{if (终止条件){处理结果return;}for (选择:本层集合中的元素(树中节点孩子的数量就是集合的大小)){处理节点BackTracking(路径,选择列表);//递归回溯,撤销处理结果}
}

组合

问题:
给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
来源:力扣(LeetCode)组合

在这里插入图片描述
思路一:这种题目我们一眼就能想到使用for循环套循环比如 k==2时

	int n = 4;for (int i = 1; i <= n; i++){for (int j = i + 1; j <= n; j++){//处理结果}}

但是如果k越来越大,我们套用的循环也会越来越多,这种暴力解法无疑是不现实的。

思路二:我们在前面说过,可以使用树的结构来模拟回溯递归的过程:
比如n=4 k=2
在这里插入图片描述
树的初始集合是[1,2,3,4],从左向右取,取过的数不再取,每次从集合中选取元素,可选择的范围逐渐缩小。有图可以发现,n相当于树的宽度,而k相当于树的深度。我们再由模板来写出最终代码:

class Solution {
public:vector<vector<int>> arr;//存放符合条件的集合vector<int> _arr;//用来存放符合条件的单一数据void BackTracking(int n, int k, int begin){if (_arr.size() == k)//递归终止条件{arr.push_back(_arr);//单一数据存放至总集合里return;}for (int i = begin; i <= n; i++)//控制树的横向遍历{_arr.push_back(i);//处理节点BackTracking(n, k, i + 1);//递归,控制树的纵向遍历,即深度_arr.pop_back();//回溯,撤销处理的节点}}vector<vector<int>> combine(int n, int k) {BackTracking(n, k, 1);return arr;}
};

剪枝优化

如果出现下面情况:
n=4 k=4
那么在第一层for循环中,从元素2开始的遍历都没有意义,因为满足k的数量不够了,所以有图可知,打叉的地方都可以优化掉
在这里插入图片描述
优化过程:

  1. 已经选择的元素个数:_arr.size()
  2. 还需要的元素个数:k - _arr.size()

优化后的代码:

class Solution {
public:vector<int> _arr;vector<vector<int>> arr;void BackTracking(int n, int k, int begin){if (_arr.size() == k){arr.push_back(_arr);return;}for (int i = begin; i <= n-(k-_arr.size())+1; i++)//剪枝优化{_arr.push_back(i);BackTracking(n, k, i + 1);_arr.pop_back();}}vector<vector<int>> combine(int n, int k) {BackTracking(n, k, 1);return arr;}
};

组合总和 III

问题:
找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。
来源:力扣(LeetCode)组合总和 III

在这里插入图片描述

思路:这个题相对于上一个题来说,就是k为树的深度,而集合固定为1到9,也就是树的宽度为9
比如:k=2 只取两个数
在这里插入图片描述
代码:

class Solution {
public:vector<vector<int>> arr;vector<int> _arr;void BackTracking(int k,int n,int begin,int sum){if(_arr.size()==k)//终止条件{if(sum==n)//满足题意{arr.push_back(_arr);}return;}for(int i=begin;i<=9;i++)//横向遍历{sum+=i;//收集元素总和_arr.push_back(i);//收集元素BackTracking(k,n,i+1,sum);//递归,纵向遍历sum-=i;//回溯_arr.pop_back();//回溯}}vector<vector<int>> combinationSum3(int k, int n) {BackTracking(k,n,1,0);return arr;}
};

剪枝优化

如果我们选择的元素总和已经大于n,那么我们再往后遍历的总和肯定也大于n,就没有继续遍历下去的意义了。元素个数方面,同样与上一题一样能继续优化。
在这里插入图片描述
优化后:

class Solution {
public:vector<vector<int>> arr;vector<int> _arr;void BackTracking(int k,int n,int begin,int sum){if(sum>n)//剪枝条件{return;}if(_arr.size()==k){if(sum==n){arr.push_back(_arr);}return;}for(int i=begin;i<=9-(k-_arr.size())+1;i++)//元素个数的优化{sum+=i;_arr.push_back(i);BackTracking(k,n,i+1,sum);sum-=i;_arr.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {BackTracking(k,n,1,0);return arr;}
};

相关文章:

面试热点题:回溯算法之组合 组合与组合总和 III

什么是回溯算法&#xff1f; 回溯算法也可以叫回溯搜索算法&#xff0c;回溯是递归的"副产品",回溯的本质是穷举&#xff0c;然后选出我们需要的数据&#xff0c;回溯本身不是特别高效的算法&#xff0c;但我们可以通过"剪枝"来优化它。 理解回溯算法 回溯…...

java面试-jvm

JVM JVM 是 java 虚拟机&#xff0c;简单来说就是能执行标准 java 字节码的虚拟计算机 JVM 是如何工作的 首先程序在执行之前先要把 Java 代码&#xff08;.java&#xff09;转换成字节码&#xff08;.class&#xff09;&#xff0c;JVM 通过类加载器&#xff08;ClassLoade…...

vscode下载与使用

1.vscode下载 官网下载地址&#xff1a;Download Visual Studio Code - Mac, Linux, Windows下载太慢&#xff0c;推荐文章&#xff1a;解决VsCode下载慢问题_vscode下载太慢_迷小圈的博客-CSDN博客下载太慢&#xff0c;推荐下载链接&#xff1a;https://vscode.cdn.azure.cn/s…...

人员摔倒识别预警算法 opencv

人员摔倒识别预警算法通过opencv网络模型技术&#xff0c;人员摔倒识别预警算法能够智能检测现场画面中人员有没有摔倒&#xff0c;无需人为干预可以立刻抓拍告警。OpenCV的全称是Open Source Computer Vision Library&#xff0c;是一个跨平台的计算机视觉处理开源软件库&…...

华为OD机试题 - 火星文计算(JavaScript)| 机考必刷

更多题库,搜索引擎搜 梦想橡皮擦华为OD 👑👑👑 更多华为OD题库,搜 梦想橡皮擦 华为OD 👑👑👑 更多华为机考题库,搜 梦想橡皮擦华为OD 👑👑👑 华为OD机试题 最近更新的博客使用说明本篇题解:火星文计算题目输入输出示例一输入输出说明Code解题思路版权说明…...

AI人工智能 - 初探

1.应用场景 主要用于了解和系统学习AI&#xff0c;从而可以在工作生活中利用AI做一些事。 2.学习/操作 1.文档阅读 下面的内容来自于与chatGPT的对话 2.整理输出 介绍AI 人工智能&#xff08;Artificial Intelligence&#xff0c;简称AI&#xff09;是计算机科学中的一个分支&…...

Spring-AOP工作流程

Spring-AOP工作流程 3&#xff0c;AOP工作流程 3.1 AOP工作流程 由于AOP是基于Spring容器管理的bean做的增强&#xff0c;所以整个工作过程需要从Spring加载bean说起: 流程1:Spring容器启动 容器启动就需要去加载bean,哪些类需要被加载呢?需要被增强的类&#xff0c;如:B…...

C51---串口发送指令,控制LED灯亮灭

1.Code: #include "reg52.h" #include "intrins.h" sfr AUXR 0x8E; sbit D5 P3^7; void UartInit(void) //9600bps11.0592MHz { //PCON & 0x7F; //波特率不倍速 AUXR 0x01; SCON 0x50; //8位数据,可变波…...

【Wiki】XWiki数据备份

XWiki为主题使用java开发的开源wiki&#xff0c;官网地址如下&#xff1a; https://www.xwiki.org/xwiki/bin/view/Main/ 目录1、 XWiki升级数据备份1.1、 获取XWiki配置的数据库与持久化目录信息1.2 备份数据库信息1.3 备份持久化目录2、XWiki数据迁移如果一个知识库不能确保数…...

ctk框架开发Qt插件应用示例工程

目录 前言 约定 插件工程pluginApp: 主启动工程StartApp: 效果演示 结语...

spring5源码篇(4)——beanFactoryPostProcessor执行/注解bean的装配

spring-framework 版本&#xff1a;v5.3.19 前面研究了beanDefinition的注册&#xff0c;但也仅仅是注册这一动作。那么在spring容器启动的过程中&#xff0c;是何时/如何装配的&#xff1f;以及装配的bean是如何注入的&#xff1f; &#xff08;考虑到xml方式基本不用了以及篇…...

masstransit的message几个高级用法

1&#xff09;问题&#xff0c;Class MessageA 基类&#xff0c;Class MessageB继承自MessageA&#xff1b; 用bus.Publish方法本想把有些消息只发给B队列&#xff0c;结果由于其继承关系A队列也获得了消息&#xff1b; 解决方法用send&#xff0c; Uri uri new Uri(RabbitM…...

漏洞分析丨cve-2012-0003

作者:黑蛋一、漏洞简介这次漏洞属于堆溢出漏洞&#xff0c;他是MIDI文件中存在的堆溢出漏洞。在IE6&#xff0c;IE7&#xff0c;IE8中都存在这个漏洞。而这个漏洞是Winmm.dll中产生的。二、漏洞环境虚拟机调试工具目标软件辅助工具XP-SP3、KaliOD、IDAIE6Windbg组件gflags.exe三…...

rm命令——删除文件或目录

rm命令是英文单词remove的缩写&#xff0c;主要功能是删除文件或目录。 因为删除文件是一个破坏性动作&#xff0c;因此&#xff0c;在使用时需要格外小心&#xff0c;在执行之前一定要再三确认删除的是哪个目录中的什么文件。 rm命令的语法格式如下&#xff1a; rm [选项] …...

【零基础入门学习Python---Python的基本语法使用】

一.Python基本语法使用 Python是一种易学且功能强大的编程语言,具有简洁的语法和广泛的应用领域。在本文中,我们将介绍Python的基本语法使用,以帮助初学者快速入门Python编程。 1.1 注释 Python 支持两种类型的注释:单行注释和多行注释。 单行注释:以 # 符号开头,从 # …...

数据仓库相关概念的解释

数据仓库相关概念的解释 文章目录数据仓库相关概念的解释1 ETL是什么&#xff1f;ETL体系结构2 数据流向何为数仓DW3 ODS 是什么&#xff1f;4 数据仓库层DWDWD 明细层DWD 轻度汇总层&#xff08;MID或DWB&#xff0c;data warehouse basis&#xff09;DWS 主题层&#xff08;D…...

1/4车、1/2车、整车悬架模糊PID控制仿真合集

目录 前言 1. 1/4悬架系统 1.1数学模型 1.2仿真分析 2. 1/2悬架系统 2.1数学模型 2.2仿真模型 2.3仿真分析 3. 整车悬架系统 3.1数学模型 3.2仿真分析 4.总结 前言 前面几篇文章介绍了LQR、SkyHook、H2/H∞、PID控制&#xff0c;接下来会继续介绍滑模、反步法、M…...

Linux性能补丁升级,避免不必要的跨核Wake-Up

导读一个由英特尔发起的、旨在改进Linux内核公平调度程序代码的补丁系列&#xff0c;也看到了来自AMD工程师和其他利益相关者的测试/反馈&#xff0c;并继续进行改进。这个补丁系列的重点是避免在不必要的情况下发生过多的跨核唤醒(Cross-CPU Wake-up)。这样一来&#xff0c;这…...

Spring Cloud Alibaba全家桶(六)——微服务组件Sentinel介绍与使用

前言 本文小新为大家带来 微服务组件Sentinel介绍与使用 相关知识&#xff0c;具体内容包括分布式系统存在的问题&#xff0c;分布式系统问题的解决方案&#xff0c;Sentinel介绍&#xff0c;Sentinel快速开始&#xff08;包括&#xff1a;API实现Sentinel资源保护&#xff0c;…...

拼多多2021笔试真题集 -- 3. 多多的求和计算

多多的求和计算 多多路上从左到右有N棵树&#xff08;编号1&#xff5e;N&#xff09;&#xff0c;其中第i个颗树有和谐值Ai。 多多鸡认为&#xff0c;如果一段连续的树&#xff0c;它们的和谐值之和可以被M整除&#xff0c;那么这个区间整体看起来就是和谐的。 现在多多鸡想请…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...