代码随想录算法训练营第二十四天|理论基础 77. 组合

 理论基础 

其实在讲解二叉树的时候,就给大家介绍过回溯,这次正式开启回溯算法,大家可以先看视频,对回溯算法有一个整体的了解。

题目链接/文章讲解:代码随想录

视频讲解:带你学透回溯算法(理论篇)| 回溯法精讲!_哔哩哔哩_bilibili

 77. 组合  

对着 在 回溯算法理论基础 给出的 代码模板,来做本题组合问题,大家就会发现 写回溯算法套路。

在回溯算法解决实际问题的过程中,大家会有各种疑问,先看视频介绍,基本可以解决大家的疑惑。

本题关于剪枝操作是大家要理解的重点,因为后面很多回溯算法解决的题目,都是这个剪枝套路。 

题目链接/文章讲解:代码随想录

视频讲解:带你学透回溯算法-组合问题(对应力扣题目:77.组合)| 回溯法精讲!_哔哩哔哩_bilibili

剪枝操作:带你学透回溯算法-组合问题的剪枝操作(对应力扣题目:77.组合)| 回溯法精讲!_哔哩哔哩_bilibili

时间复杂度: O(n * 2^n)
空间复杂度: O(n)List<List<Integer>> result= new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {backtracking(n,k,1);return result;}public void backtracking(int n,int k,int startIndex){if (path.size() == k){result.add(new ArrayList<>(path));return;}for (int i =startIndex;i<=n;i++){path.add(i);backtracking(n,k,i+1);path.removeLast();}}

剪枝:

可以剪枝的地方就在递归中每一层的for循环所选择的起始位置

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了,那么就没有必要搜索了

 List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {combineHelper(n, k, 1);return result;}/*** 每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围,就是要靠startIndex* @param startIndex 用来记录本层递归的中,集合从哪里开始遍历(集合就是[1,...,n] )。*/private void combineHelper(int n, int k, int startIndex){//终止条件if (path.size() == k){result.add(new ArrayList<>(path));return;}for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){path.add(i);combineHelper(n, k, i + 1);path.removeLast();}}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/122820.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

函数栈帧(详解)

一、前言&#xff1a; 环境&#xff1a;X86Vs2013 我们C语言学习过程中是否遇到过如下问题或者疑惑&#xff1a; 1、局部变量是如何创建的&#xff1f; 2、为什么局部变量的值是随机值&#xff1f; 3、函数是怎么传参的&#xff1f;传参的顺序是怎样的&#xff1f; 4、形…

HarmonyOS/OpenHarmony(Stage模型)应用开发单一手势(三)

五、旋转手势&#xff08;RotationGesture&#xff09; RotationGesture(value?:{fingers?:number; angle?:number}) 旋转手势用于触发旋转手势事件&#xff0c;触发旋转手势的最少手指数量为2指&#xff0c;最大为5指&#xff0c;最小改变度数为1度&#xff0c;拥有两个可…

3D异常检测论文笔记 | Shape-Guided Dual-Memory Learning for 3D Anomaly Detection

文章目录 摘要一、介绍三、方法3.1. 形状引导专家学习3.2. Shape-Guided推理 摘要 我们提出了一个形状引导的专家学习框架来解决无监督的三维异常检测问题。我们的方法是建立在两个专门的专家模型的有效性和他们的协同从颜色和形状模态定位异常区域。第一个专家利用几何信息通…

机器学习笔记:node2vec(论文笔记:node2vec: Scalable Feature Learning for Networks)

2016 KDD 1 intro 利用graph上的节点相似性&#xff0c;对这些节点进行embedding 同质性&#xff1a;节点和其周围节点的embedding比较相似 蓝色节点和其周围的节点结构等价性 结构相近的点embedding相近 比如蓝色节点&#xff0c;都处于多个簇的连接处 2 随机游走 2.1 介绍…

『C语言进阶』指针进阶(一)

&#x1f525;博客主页&#xff1a; 小羊失眠啦 &#x1f516;系列专栏&#xff1a; C语言 &#x1f325;️每日语录&#xff1a;无论你怎么选&#xff0c;都难免会有遗憾。 ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 前言 在C语言初阶中&#xff0c;我们对指针有了一定的…

《机器人学一(Robotics(1))》_台大林沛群 第 5 周【机械手臂 轨迹规划】 Quiz 5

我又行了&#xff01;&#x1f923; 求解的 位置 可能会有 变动&#xff0c;根据求得的A填写相应值即可。注意看题目。 coursera链接 文章目录 第1题 Cartesian space求解 题1-3 的 Python 代码 第2题第3题第4题 Joint space求解 题4-6 的 Python 代码 第5题第6题其它可参考代…

编写软件检测报告有哪些注意事项?软件检测报告获取

软件检测报告是指把测试的过程和结果写成文档&#xff0c;对发现的问题和缺陷进行分析&#xff0c;为纠正软件的存在的质量问题提供依据&#xff0c;同时为软件验收和交付打下基础。 一、编写软件检测报告的注意事项 1、报告的结构要合理和清晰。应该按照一定的逻辑顺序&…

解决 Spring Boot 与 springfox 的 NullPointerException 问题

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…

MySQL误删数据 回滚

前言 生产环境数据库不允许删除表&#xff0c;可以将表修改成 XXX_to_delete 如果误删简单数据&#xff0c;可以考虑使用binlog恢复 一、查看命令 1.查看binlog是否开启 show variables like log_bin;切换到MySQL安装目录,查看mysqlbinlog日志文件 2.查看所有 binlog 日志…

Ansible学习笔记12

playbook&#xff1a; playbook&#xff08;剧本&#xff09;&#xff1a;是ansible用于配置、部署和管理被控节点的剧本&#xff0c;用于Ansible操作的编排。 使用的是yaml格式&#xff0c;&#xff08;saltstack、elk、docker、docker-compose、k8s都会使用到yaml格式。&am…

【c++ debug】cmake编译报错 No such file or directory

1. 报错&#xff1a;error while loading shared libraries: libprotoc.so.24: cannot open shared object file: No such file or directory 问题原因&#xff1a;找不到动态库 解决方法&#xff1a;添加动态库路径 export LD_LIBRARY_PATH$LD_LIBRARY_PATH:/your/protobuf/l…

【C语言】入门——结构体

目录 结构体 为什么有结构体&#xff1f; 1.结构体的声明 1.2结构体变量的访问和初始化 2.结构体成员的访问 结构体 struct 结构体类型 {//相关属性; }结构体变量; 结构体和数组不同&#xff0c;同一类型的数据的集合是数组&#xff1b; 结构体是多种类型的数据的集合&…

【Java Web】统一处理异常

一个异常处理的ControllerAdvice类。它用于处理Controller注解的控制器中发生的异常。 具体代码功能如下&#xff1a; 导入相关类和方法。声明一个Logger对象&#xff0c;用于日志记录。使用ExceptionHandler注解标记handleException方法&#xff0c;用于处理所有异常。 -嘛在…

C++——shared_ptr:make_shared的用处,与shared_ptr直接构造的区别

shared_ptr shared_ptr继承自__shared_ptr&#xff0c;其中有两个对象&#xff0c;一个是指向资源的指针&#xff0c;一个是控制块&#xff0c;指向一个引用计数对象。控制块中存储了强引用和弱引用的计数&#xff0c;强引用Uses代表shared_ptr对象的引用计数&#xff0c;弱引…

每日一题 1921. 消灭怪物的最大数量

难度&#xff1a;中等 思路&#xff1a; 已知速度和距离&#xff0c;可求时间必定先消灭时间最短的怪物求得时间数组排序&#xff0c;只要在第 i 秒时&#xff0c;time[i] > i &#xff0c;那么就可以消灭第 i 个怪物 代码&#xff1a; class Solution:def eliminateMax…

Leetcode刷题笔记--Hot41-50

1--二叉树的层序遍历&#xff08;102&#xff09; 主要思路&#xff1a; 经典广度优先搜索&#xff0c;基于队列&#xff1b; 对于本题需要将同一层的节点放在一个数组中&#xff0c;因此遍历的时候需要用一个变量 nums 来记录当前层的节点数&#xff0c;即 nums 等于队列元素的…

存储过程报Illegal mix of collations错误的解决方法

CREATE PROCEDURE maxAgeStudent(IN _gender CHAR) BEGINDECLARE maxage INT DEFAULT 0;SELECT max(age) INTO maxage FROM student where gender _gender;SELECT * from student WHERE age maxage and gender _gender; END; 在调用的时候 call maxAgeStudent(1) 产生了报…

Linux之DNS域名解析服务

目录 Linux之DNS域名解析服务 概述 产生原因 作用 连接方式 因特网的域名结构 拓扑 分类 域名服务器类型 ​编辑 DNS域名解析过程 分类 解析图 搭建DNS域名解析服务器 概述 安装软件 bind服务中三个关键文件 主配置文件分析 一般需要修改三部分&#xff1a;…

核辐射检测仪电子测量方案

核辐射检测仪又名辐射检测仪&#xff0c;主要是安检、海关、实验室、金属探测公司等行业使用。但由于2023年8月24日排放核废水&#xff0c;导致海洋遭受核辐射污染&#xff0c;由于大海的净化能力有限&#xff0c;则会导致核废水有可能随着洋流的运动&#xff0c;会流至我国海域…

Python列表排序

介绍一个关于列表排序的sort方法&#xff0c;看下面的案例&#xff1a; """ 列表的sort方法来对列表进行自定义排序 """# 准备列表 my_list [["a", 33], ["b", 55], ["c", 11]]# 排序&#xff0c;基于带名函数 …