回溯算法之简单组合

哦吼!今天结束了二叉树,开始回溯算法

其实也需要用到迭代,哈哈哈哈,但是这个暴力穷举真的好爽。

先记一下回溯算法的基本框架吧

老规矩:

还是有结束条件

但是后面就不太一样了

这里就是for循环,循环n次(相当于n叉树)是不是很酷,终于感觉到二叉树学了点啥了

很简单,框架就已经写好了

下面看一道题目:

给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1:

输入:n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

思路:

利用穷尽回溯法

按照循环遍历 i 到 n 的数,在里面再次遍历 然后再遍历再遍历,直到把所有的数都遍历一遍。终止条件就是size达到k时

这个还是可以看的很清楚的

下面来看看代码吧

class Solution {
public:
    vector<int> rus;
    vector<vector<int>> result;
    void backtraing(int n,int k,int startIndex)
    {
        if(rus.size() == k)
        {
            result.push_back(rus);
            return;
        }
        for(int i = startIndex; i <= n; i++)
        {
            rus.push_back(i);
            backtraing(n,k,i+1);
            rus.pop_back();
        }
        return;
    }

    vector<vector<int>> combine(int n, int k) 
    {
        backtraing(n,k,1);
        return result;
    }
};

其实还是可以对这个算法进行优化的,比如我的n是8,k是5

那么从1,2,3,4开始都是可以要的,但是到了5,因为后面就算全部都要也凑不到5个数,所以就不用取遍历后面的数了,这个操作也叫剪枝操作

也就是要在i<这里进行修改,那么i小于多少呢,i小于n - (k-path.size()) +1

加1是因为左闭的原则,可以 n - (k-path.size()) +1 这个式子的含义是,当前可以的最大开始数

看修改后代码

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 优化的地方
            path.push_back(i); // 处理节点
            backtracking(n, k, i + 1);
            path.pop_back(); // 回溯,撤销处理的节点
        }
    }
public:

    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
};

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

系统思考的魅力

“不管你信不信&#xff0c;你的系统正是为了现在这个结果而设计的。”—爱德华兹戴明 在长期的组织辅导中&#xff0c;最开始我常听到管理者们说&#xff1a;“这是某某的问题”&#xff0c;或者“某某真不行”。我想这也正显示出系统思考的真正魅力&#xff0c;当大家开始用…

小波相干性显著性检验(MATLAB R2018A)

交叉小波常被用于检测不同信号之间的相关性&#xff0c;其在时频域建立了不同信号之间的联系。对于两个时域信号&#xff0c;其交叉小波变换和交叉小波尺度谱如下&#xff1a; 以轴承振动信号为例&#xff0c;利用正常轴承与故障轴承的振动信号、故障轴承和故障轴承的振动信号分…

使用conda环境安装pythonocc-core

conda环境安装pythonocc库 基本环境 操作系统:Ubuntu 22.04 conda 23.11.0 安装pythonocc-core conda create --name pyocc python3.10 conda activate pyocc conda install -c conda-forge pythonocc-core7.8.1也可参考下面的官方地址 pythonocc-core 官方git地址 conda官…

Golang | Leetcode Golang题解之第128题最长连续序列

题目&#xff1a; 题解&#xff1a; func longestConsecutive(nums []int) int {numSet : map[int]bool{}for _, num : range nums {numSet[num] true}longestStreak : 0for num : range numSet {if !numSet[num-1] {currentNum : numcurrentStreak : 1for numSet[currentNum…

第4章:车辆的横向优化控制

4.1 车辆动力学模型 注1&#xff1a;运动学模型和动力学模型最大的不同点在于 运动学模型是在我们不考虑车辆的受力情况下建立的&#xff08;回顾我们推导出运动学模型的过程&#xff0c;我们没有使用到任何车辆所受的外力作为公式中的已知量&#xff0c;而是直接通过 “ 车速…

力扣173题:二叉搜索树迭代器(含模拟面试)

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容&#xff0c;和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣&#xff01; 推荐&#xff1a;数据分析螺丝钉的首页 关注微信公众号 数据分析螺丝钉 免费领取价值万元的python/java/商业…

OBS实现多路并发推流

OBS实现多路并发推流 解决方案速览相关依赖下载安装多路推流 解决方案速览 利用OBS进行本地直播画面的构建。 使用Multiple RTMP outputs plugin进行多路并发推流。 相关依赖下载安装 OBS软件 # OBS官网 https://obsproject.com/zh-cnMultiple RTMP outputs plugin # 插件官网…

【TB作品】MSP430 G2553 单片机口袋板,流水灯,按键改变花型

功能 按键修改流水灯的花型&#xff0c;一共四种花型。 效果 部分代码 while (1){PinIN();I2C_IODect(); /*按键检测处理 */delay_ms(20);time;if (time > 6){time 0;if (mode 0){index;if (index > 7){index 0;}PinOUT(0, 1); /* 指定0号管脚输出为0 */PinOUT(1, 1)…

视觉盛宴:探索大屏UI设计的卓越美学

视觉盛宴&#xff1a;探索大屏UI设计的卓越美学 在数字时代&#xff0c;用户界面&#xff08;UI&#xff09;设计不仅仅是功能性的体现&#xff0c;更是美学与技术融合的艺术。大屏UI设计&#xff0c;以其独特的视觉冲击力和交互体验&#xff0c;为用户带来了前所未有的视觉盛…

【Web API DOM03】事件监听

一&#xff1a;什么是事件监听 指程序检测有无某一事件发生&#xff0c;如果发生&#xff0c;就调用一个函数做出反应&#xff1b;也称为绑定事件或注册事件 比如鼠标经过显示下拉菜单、点击侧边栏播放轮播图 二&#xff1a;怎么用事件监听 1 语法规范&#xff1a; 元素对…

node.js安装步骤

系统重装node.js&#xff0c;记录一下步骤。 我的项目使用的版本是v14.13.0&#xff0c;到官网下载一下二进制压缩包。 下载完成后&#xff0c;解压压缩包到自己想要的路径。然后进行环境变量设置。 经过这两步以后&#xff0c;使用控制台就可以查看node的版本了。

随心笔记,第五更

目录 脚本代码 启动方式 开机自启 1、打开“任务计划程序”&#xff1a; 2、创建基本任务&#xff1a; 3、触发任务&#xff1a; 4、执行任务&#xff1a; 5、编辑任务&#xff1a; 6、完成设置&#xff1a; 手动启动 示例代码&#xff08;Python脚本自启&#xff0…

算法每日一题(python,2024.06.02)

题目来源&#xff1a;&#xff08;力扣. - 力扣&#xff08;LeetCode&#xff09;&#xff0c;简单&#xff09; 解题思路&#xff1a; 用lower()函数转换为小写&#xff08;也可以用upper()函数全部变为大写&#xff09;&#xff0c;用isalnum()函数去除非字母数字字符&#…

【Linux】进程(3):运行,阻塞,挂起

大家好&#xff0c;我是苏貝&#xff0c;本篇博客带大家了解Linux进程&#xff08;3&#xff09;&#xff0c;如果你觉得我写的还不错的话&#xff0c;可以给我一个赞&#x1f44d;吗&#xff0c;感谢❤️ 目录 &#xff08;A&#xff09; 运行&#xff08;R&#xff09;进程切…

Java | Leetcode Java题解之第127题单词接龙

题目&#xff1a; 题解&#xff1a; class Solution {Map<String, Integer> wordId new HashMap<String, Integer>();List<List<Integer>> edge new ArrayList<List<Integer>>();int nodeNum 0;public int ladderLength(String beginW…

计算机网络学习实践:配置主机通过DHCP获取IP并通过域名访问web服务器

计算机网络学习实践&#xff1a;配置主机通过DHCP获取IP并通过域名访问web服务器 点一点就能配置&#xff0c;不需要输入命令 1.实验准备 实验环境&#xff1a;思科的模拟器 实验设备&#xff1a; 3个服务器&#xff0c;1个二层交换机&#xff08;不是三层的&#xff09;&a…

ctfshow-web入门-信息搜集(web11-web20)

目录 1、web11 2、web12 3、web13 4、web14 5、web15 6、web16 7、web17 8、web18 9、web19 10、web20 1、web11 域名其实也可以隐藏信息&#xff0c;比如flag.ctfshow.com 就隐藏了一条信息 查询域名的 DNS 记录&#xff0c;类型为 TXT&#xff08;域名的说明&#…

20、matlab信号波形生成:狄利克雷函数、高斯脉冲和高斯脉冲序列

1、狄利克雷函数生成波形diric()函数 语法&#xff1a;y diric(x,n) 返回n次的狄利克雷函数对输入数组x的元素求值。 1&#xff09;diric()函数 代码 x linspace(-2*pi,2*pi,301);%定义x取值 d6 diric(x,6); d7 diric(x,7); subplot(2,1,1) plot(x,d6) ylabel(n 6) tit…

YOLOv10:实时端到端目标检测的新突破

目标检测作为计算机视觉领域的一个核心问题&#xff0c;其关键在于能够在图像中准确识别并定位对象。随着深度学习技术的发展&#xff0c;基于深度神经网络的目标检测方法不断涌现&#xff0c;其中YOLO&#xff08;You Only Look Once&#xff09;系列算法以其优异的实时性和准…

【PB案例学习笔记】-14使用次数和日期限制

写在前面 这是PB案例学习笔记系列文章的第14篇&#xff0c;该系列文章适合具有一定PB基础的读者。 通过一个个由浅入深的编程实战案例学习&#xff0c;提高编程技巧&#xff0c;以保证小伙伴们能应付公司的各种开发需求。 文章中设计到的源码&#xff0c;小凡都上传到了gite…