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

回溯理论基础

在这里插入图片描述
回溯法解决的问题都可以抽象为树形结构,因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度,都构成的树的深度。递归就要有终止条件,所以必然是一棵高度有限的树(N叉树)。

回溯三部曲

1、回溯函数模板返回值以及参数
在回溯算法中,我的习惯是函数起名字为backtracking,这个起名大家随意。回溯算法中函数返回值一般为void。
再来看一下参数,因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来,所以一般是先写逻辑,然后需要什么参数,就填什么参数。但后面的回溯题目的讲解中,为了方便大家理解,我在一开始就帮大家把参数确定下来。
回溯函数伪代码如下:

void backtracking(参数)

2、回溯函数终止条件
既然是树形结构,那么我们在讲解二叉树的递归 (opens new window)的时候,就知道遍历树形结构一定要有终止条件。所以回溯也有要终止条件。什么时候达到了终止条件,树中就可以看出,一般来说搜到叶子节点了,也就找到了满足条件的一条答案,把这个答案存放起来,并结束本层递归。所以回溯函数终止条件伪代码如下:

if (终止条件) {
    存放结果;
    return;
}

3、回溯搜索的遍历过程
在上面我们提到了,回溯法一般是在集合中递归搜索,集合的大小构成了树的宽度,递归的深度构成的树的深度。
如图:
在这里插入图片描述

回溯算法模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}

77 组合

题目链接/文章讲解:https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html
视频讲解:https://www.bilibili.com/video/BV1ti4y1L7cv
剪枝操作:https://www.bilibili.com/video/BV1wi4y157er
在这里插入图片描述

思路:将回溯问题理解成树,重点理解每次还要pop出来

理论上这道题如果k=2可以用两层for循环嵌套,但是如果k=50就要嵌套50层for循环,因此这时候就需要用到回溯了。(k不确定,可能很大也可能很小)
在这里插入图片描述

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    let result = [];
    let path = [];
    //确定回溯的参数
    const backTracking = (n,k,start) => {
    	//终止条件
        if(path.length === k){
            //[...path]
            result.push(path.slice());
            return;
        }
        //单层循环
        for(let i = start;i<=n;i++){
            path.push(i);
            backTracking(n,k,i+1);
            path.pop();
        }
    }
    backTracking(n,k,1);
    return result;

};

使用 result.push(path.slice()) 而不是 result.push(path) 的主要原因是,JavaScript 中的数组是引用类型,如果直接使用 result.push(path),会将 path 的引用放入 result 数组中。
由于 backtracking 过程中 path 数组不断变化(不断添加和移除元素),如果直接将 path 引用放入 result 数组中,由于 backtracking 过程中 path 数组会不断更改,最终 result 数组中的所有元素都会指向相同的 path 引用,导致 result 数组中的元素都是一样的,而不是不同的组合。
因此,为了确保在 result 数组中存储不同的组合,需要使用 path.slice() 来创建 path 的副本,将副本推入 result 数组中。这样每个组合都是不同的,不会相互影响。
所以,采用 result.push(path.slice()) 会确保在 result 数组中存储不同的组合,而不是相同的引用。

剪枝

在这里插入图片描述
图中每一个节点(图中为矩形),就代表本层的一个for循环,那么每一层的for循环从第二个数开始遍历的话,都没有意义,都是无效遍历。

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

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

注意代码中i,就是for循环里选择的起始位置。

1、已经选择的元素个数:path.size();

2、还需要的元素个数为: k - path.size();

3、在集合n中至多要从该起始位置 : 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]。

因此,剪枝操作仅需要将i的范围更改即可。

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    let result = [];
    let path = [];
    const backTracking = (n,k,start) => {
        if(path.length === k){
            //[...path]
            result.push(path.slice());
            return;
        }
        for(let i = start;i <= n - (k - path.length) + 1;i++){
            path.push(i);
            backTracking(n,k,i+1);
            path.pop();
        }
    }
    backTracking(n,k,1);
    return result;

};

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

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

相关文章

仰卧起坐计数,YOLOV8POSE

仰卧起坐计数&#xff0c;YOLOV8POSE 通过计算膝盖、腰部、肩部的夹角&#xff0c;计算仰卧起坐的次数

springboot278基于JavaWeb的鲜牛奶订购系统的设计与实现

鲜牛奶订购系统的设计与实现 摘 要 如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解决一些老技术的弊端问题。因为传统鲜牛奶订购信息管理难度大&…

Python使用 k 均值对遥感图像进行语义分割

本篇文章介绍K-means语义分割来估计 2000 年至 2023 年咸海水面的变化 让我们先看一下本教程中将使用的数据。这是同一地区的两张 RGB 图像,间隔 23 年,但很明显地表特性和大气条件(云、气溶胶等)不同。这就是为什么我决定训练两个独立的 k-Means 模型,每个图像一个。 首…

水下蓝牙耳机哪个牌子好?推荐四款高人气力作游泳耳机

在这个充满活力的时代&#xff0c;人们对于生活的追求早已不仅仅局限于日常的琐碎&#xff0c;更多的是对健康、对自我挑战的向往。运动&#xff0c;成为了现代人生活中不可或缺的一部分。而游泳&#xff0c;作为一项既能锻炼全身&#xff0c;又能享受水中美妙的运动&#xff0…

广州地铁线路规划

使用python实现后端功能&#xff0c;由于地铁图需要进行展示&#xff0c;svg图需要花费比较多的时间&#xff0c;这里使用了 MetroFlow 库构建的地铁地图编辑器&#xff0c;可以在画布上构建矢量图&#xff0c;实现站点路线的创建。 用法&#xff1a; 打包好后完整目录&#x…

CornerStone之读取txt文件点数据

1. 页面标签 页面中目前只提供一个按钮来进行输入文件 <input click"importZeroOne" type"file" />2. 函数定义 在输入文件之后&#xff0c;执行importZeroOne函数&#xff0c;获得输入的文件&#xff0c;进行以下处理 const importZeroOne((eve…

windows 11访问Debian10上的共享目录

步骤 要在Windows 11上访问Debian 10.0.0的共享目录&#xff0c;可以通过以下步骤来实现&#xff1a; 1. 设置Samba服务&#xff1a;在Debian系统上&#xff0c;需要安装并配置Samba服务&#xff0c;以便能够实现文件夹共享。Samba是一个允许Linux/Unix服务器与Windows操作系…

【数据结构与算法】(15):归并排序的递归和非递归方式

&#x1f921;博客主页&#xff1a;Code_文晓 &#x1f970;本文专栏&#xff1a;数据结构与算法 &#x1f63b;欢迎关注&#xff1a;感谢大家的点赞评论关注&#xff0c;祝您学有所成&#xff01; ✨✨&#x1f49c;&#x1f49b;想要学习更多数据结构与算法点击专栏链接查看&…

二、C#选择排序算法

简介 选择排序算法的基本思想是每一次从待排序的数据元素中选出最小&#xff08;或最大&#xff09;的一个元素&#xff0c;存放在序列的起始位置&#xff0c;然后&#xff0c;再从剩余未排序元素中继续寻找最小&#xff08;大&#xff09;元素&#xff0c;然后放到已排序序列…

【ArcGISProSDK】获取扩展模块许可到期时间

结果 以下是获取的3D分析模块的许可到期时间 代码 var licenseExpirationDate ArcGIS.Core.Licensing.LicenseInformation.GetExpirationDate(LicenseCodes.Analyst3D); 扩展模块 MemberDescriptionAnalyst3D3D AnalystAviationAirportsAviation and AirportsBusinessAnal…

绿色再生·安卓4G智能远程操作巡视机器人小车

一、前言 1.1 项目介绍 【1】项目功能介绍 随着物联网技术与移动通信技术的快速发展&#xff0c;远程遥控设备在日常生活及工业应用中的普及度日益提高。无论是家用扫地机器人实现自主导航清扫&#xff0c;还是目前抖音平台上展示的实景互动小车等创新应用&#xff0c;都体现…

ICBatlas数据库-转录组免疫检查点阻断疗法数据

ICBatlas: A Comprehensive Resource for Depicting Immune Checkpoint Blockade Therapy Characteristics from Transcriptome Profiles 介绍&#xff1a;在线ICBatlas (hust.edu.cn) 检查点阻断 &#xff08;ICB&#xff09; 疗法为多种癌症类型提供了显着的临床益处。目前…

6语言交易所/多语言交易所php源码/微盘PHP源码

6语言交易所PHP源码&#xff0c;简单测试了一下&#xff0c;功能基本都是正常的。 由于是在本地测试的运行环境的问题&#xff0c;K线接口有点问题&#xff0c;应该在正式环境下是OK的。 源码下载地址&#xff1a;6语言交易所/多语言交易所php源码/微盘PHP源码.zip 程序截图…

【安装教程】安装cudnn

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 安装cudnn 前言一、下载和自己cuda匹配的cudnn二、安装cudnn 前言 首先我是已经安装了cuda&#xff0c;但是因为没有安装cudnn在跑程序的时候出现了一些问题&#xff0c;因此…

Axure 中继器的Repeater属性的使用

dataCount 中继器当中存在多少条数据&#xff0c;总数。 visibleltemCount 中继器列表中可见项数量&#xff0c;也就是当前页面显示的数量。 pageCount 获取中继器分页的总数量&#xff0c;即能够获取分页后共有多少页。 pageIndex 获取中继器当前显示的页码

【数字孪生】Nginx发布数字孪生三维建模模型服务及调用方法

【数字孪生】Nginx发布数字孪生三维建模模型服务及调用方法 一、需求二、实施步骤2.1 准备模型文件2.1.1 3D tiles模型2.1.2 3D Tiles标准文件格式 2.2 配置nginx server块2.2.1 Nginx能干啥 2.3 访问 三、实现效果 一、需求 利用三维渲染引擎Cesium加载3D tiles模型。 二、实…

上海微电子企业ERP系统介绍及现状

在当今信息化、数字化的时代&#xff0c;企业资源规划(ERP)系统已成为企业管理的核心工具。上海微电子企业&#xff0c;作为国内微电子行业的重要力量&#xff0c;其ERP系统的应用与发展更是备受关注。 ERP系统是一种集信息技术与管理思想于一体的企业管理系统。它通过对企业内…

无人咖啡机品质之选,D 咖助力差异化竞争

在当今竞争激烈的商业环境中&#xff0c;如何脱颖而出成为众多企业关注的焦点。而无人咖啡机的出现&#xff0c;为商家提供了一个全新的思路。D 咖无人咖啡机&#xff0c;以其卓越的品质和独特的功能&#xff0c;成为了商家们实现差异化竞争的得力助手。 1. 卓越品质&#xff1…

uniapp——第4篇:分析一下全局文件、配置

前提&#xff0c;建议先学会前端几大基础&#xff1a;HTML、CSS、JS、Ajax&#xff0c;还有一定要会Vue!&#xff08;Vue2\Vue3&#xff09;都要会&#xff01;&#xff01;&#xff01;不然不好懂 一、uniapp项目创建新包放乱杂文件 我们的项目结构里有一个包叫static&#x…

Python环境下基于1D-CNN、2D-CNN和LSTM的一维信号分类

以简单的西储大学轴承数据集为例&#xff0c;随便你下载几个信号玩耍吧&#xff0c;我选了10个信号&#xff0c;分别求为正常状态&#xff0c;内圈&#xff08;轻、中和重度损伤&#xff09;&#xff0c;外圈&#xff08;轻、中和重度损伤&#xff09;&#xff0c;滚动体&#…