leetcode77组合——经典回溯算法
本文主要讲解组合的要点与细节,以及回溯算法的解题步骤,按照步骤思考更方便理解
c++和java代码如下,末尾
给定两个整数
n和k,返回范围[1, n]中所有可能的k个数的组合。你可以按 任何顺序 返回答案。
具体要点:
1. 首先,这道题的暴力解法是k层for循环,遍历所有的情况。但是这样子时间复杂度会很高。所以对于这类排列组合的问题,通常我们使用回溯算法来进行遍历,可以花一分钟参考回溯的前言概述。
2. 然后让我们来回顾一下回溯,回溯本质是一个树结构通常是由两个结构组成:for+递归。
其中,for用来表示树的宽度,遍历每层的集合元素集,可以理解一个节点有多少个孩子,这个for循环就执行多少次。
递归用来表示树的深度
3. 对于本题要求,我们需要先创建两个数组,一个用来存放最终的结果,一个用来存放过程中每次的结果
vector<vector<int>> res; //用来存放最终的结果
vector<int> temp; //用来存放过程中每次的结果
4. 接着我们就可以考虑回溯算法的实现,具体包括两部分:for循环+递归
首先,我们来考虑递归,说到递归,就要思考递归三要素:
- 递归函数参数与返回值
- 终止条件
- 单层递归逻辑
返回值:由于我们是直接操作数组,不像二叉树一样需要返回节点,所以递归的返回值是void
参数:回溯算法中的递归参数较多,我们在写代码过程中慢慢添加
终止条件:也就是我们收集结果的条件,当我们的temp存放的数量等于k时,就需要收集结果了
单层递归逻辑:添加当前元素a到temp中——a向下递归——移除刚才添加的元素a
其次,让我们考虑一下for循环的细节
for循环的起始值应该是什么呢?
这个细节是回溯中重要的点,因为本题是“组合”,所以不需要顺序,即{1,2}和{2,1}是一个意思,只保留一个,所以下一层递归时,起始值就+1,从而达到去重的目的。
void backtracing(int n, int k,vector<vector<int>>& res, vector<int> temp,int start) {//终止条件if (temp.size() == k) {//收集结果res.push_back(temp);return;}for (int i = start; i <= n; ++i) {temp.push_back(i);//添加当前元素backtracing(n, k, res, temp, i + 1);//相下递归,起始值+1temp.pop_back();//删除刚才添加的元素,实现回溯}return;}
以上就是回溯的整体逻辑,让我们总结一下重要的细节:
- 递归的返回值
- 递归的终止条件
- for循环的起始值
在回溯过程中大家重点思考一下这几个细节点,有助于我们更好的实现代码
如果觉得我的讲解有一点帮助,十分感谢您的喜欢。
c++代码:
#include<bits/stdc++.h>
using namespace std;class Solution {
public:vector<vector<int>> combine(int n, int k) {//组合,不考虑顺序vector<vector<int>> res;vector<int> temp;backtracing(n, k, res, temp, 1);return res;}void backtracing(int n, int k,vector<vector<int>>& res, vector<int> temp,int start) {//终止条件if (temp.size() == k) {//收集结果res.push_back(temp);return;}for (int i = start; i <= n; ++i) {temp.push_back(i);//添加当前元素backtracing(n, k, res, temp, i + 1);//相下递归temp.pop_back();//删除刚才添加的元素,实现回溯}return;}};
java代码
class Solution {public List<List<Integer>> combine(int n, int k) {List<List<Integer>> res = new ArrayList<List<Integer>>();List<Integer> temp = new ArrayList<>();backtracking(n, k, res, temp, 1);return res;}public void backtracking(int n, int k, List<List<Integer>> res, List<Integer> temp, int start) {//终止条件if (temp.size() == k) {res.add(new ArrayList<>(temp));return;}for (int i = start; i <= n; i++) {temp.add(i);backtracking(n, k, res, temp, i + 1);temp.remove(temp.size() - 1);}return;}
}
相关文章:
leetcode77组合——经典回溯算法
本文主要讲解组合的要点与细节,以及回溯算法的解题步骤,按照步骤思考更方便理解 c和java代码如下,末尾 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 具体要点: …...
springcloud-alibba之FeignClient
代码地址:springcloud系列: springcloud 组件分析拆解 1.FeignClient的集成 springboot版本:3.1.5 springcloud组件版本:2022.0.4 nacos客户端的版本:2.3.2 1.引pom 这里引入了nacos和feginclient的版本 <dependency>…...
三、docker配置阿里云镜像仓库并配置docker代理
一、配置阿里云镜像仓库 1. 登录阿里云官网,并登录 https://www.aliyun.com/ 2. 点击产品 - 容器 - 容器与镜像服务ACR - 管理控制台 - 镜像工具 - 镜像加速器 二、配置docker代理 #1. 创建docker相关的systemd文件 mkdir -p /etc/systemd/system/docker.servic…...
【面向就业的Linux基础】从入门到熟练,探索Linux的秘密(十一)-git(3)
Git是目前最流行的版本控制系统之一,在现代软件开发中扮演着重要的角色。它能够有效地跟踪文件变化、协作开发,并存储项目的历史记录。本文的目的是向读者介绍Git的基本概念和工作原理,帮助初学者快速上手使用Git,并帮助有经验的开…...
全面解析 TypeScript 泛型的二三事
2024年了相信大家都已经在日常开发的过程中使用上了 TypeScript 了。TypeScript 增强了代码可靠性和可维护性,确保减少运行时错误并提高开发人员的工作效率。 TypeScript 通过类型声明 使得 javascript 拥有了强类型校验。而泛型的是类型声明中最重要的一环&#x…...
单/多线程--协程--异步爬虫
免责声明:本文仅做技术交流与学习... 目录 了解进程和线程 单个线程(主线程)在执行 多线程 线程池 协程(爬虫多用) 假异步:(同步) 真异步: 爬虫代码模版 异步-爬虫 同步效果--19秒 异步效果--7秒 了解进程和线程 # --------------------> # ------> # …...
android pdf框架-11,查看图片
前10篇文章,9章关于pdf的,pdf解析后,里面也是有各种图片,于是利用pdf的view来展示图片,似乎也是个不错的想法. android手机中的图片查看功能,有的可以展示,有的不能.比如华为,荣耀对大体积的png是可以显示的,小米是不显示,只有缩略图. 一张png50m大,比如清明上河图,原图是tif…...
【CSS】深入浅出弹性布局
CSS的弹性布局(Flexbox)是一种用于在容器中沿着一维方向(水平或垂直)来布局、对齐和分配容器内项目空间的有效方式。它旨在提供一个更加有效的方式来布局、对齐和分配容器中项目的空间,即使它们的大小未知或是动态变化…...
医院挂号系统小程序的设计
管理员账户功能包括:系统首页,个人中心,患者管理,医生管理,专家信息管理,科室管理,预约信息管理,系统管理 微信端账号功能包括:系统首页,专家信息࿰…...
广州外贸建站模板
Yamal外贸独立站wordpress主题 绿色的亚马尔Yamal外贸独立站wordpress模板,适用于外贸公司建独立站的wordpress主题。 https://www.jianzhanpress.com/?p7066 赛斯科Sesko-W外贸建站WP主题 适合机械设备生产厂家出海做外贸官网的wordpress主题,红橙色…...
KDP数据分析实战:从0到1完成数据实时采集处理到可视化
智领云自主研发的开源轻量级Kubernetes数据平台,即Kubernetes Data Platform (简称KDP),能够为用户提供在Kubernetes上的一站式云原生数据集成与开发平台。在最新的v1.1.0版本中,用户可借助 KDP 平台上开箱即用的 Airflow、AirByte、Flink、K…...
【人工智能】-- 智能机器人
个人主页:欢迎来到 Papicatch的博客 课设专栏 :学生成绩管理系统 专业知识专栏: 专业知识 文章目录 🍉引言 🍉机器人介绍 🍈机器人硬件 🍍机械结构 🍍传感器 🍍控…...
Android广播机制
简介 某个网络的IP范围是192.168.0.XXX,子网 掩码是255.255.255.0,那么这个网络的广播地址就是192.168.0.255。广播数据包会被发送到同一 网络上的所有端口,这样在该网络中的每台主机都将会收到这条广播。为了便于进行系统级别的消息通知&…...
SQL FOREIGN KEY
SQL FOREIGN KEY 简介 SQL(Structured Query Language)是用于管理关系数据库管理系统(RDBMS)的标准编程语言。在SQL中,FOREIGN KEY是一个重要的概念,用于建立和维护数据库中不同表之间的关系。本文将详细介绍SQL FOREIGN KEY的概念、用途、以及如何在SQL中实现和使用FO…...
绘唐3最新版本哪里下载
绘唐3最新版本哪里下载 绘唐最新版本下载地址 推文视频创作设计是一种通过视频和文字的形式来进行推广的方式,可以通过一些专业的工具来进行制作。 以下是一些常用的小说推文视频创作设计工具: 视频剪辑软件:如Adobe Premiere Pro、Fina…...
[ES6] 箭头函数
JavaScript 是一种广泛使用的编程语言,随着其发展和演变,引入了很多新的特性来提高代码的可读性和开发效率。其中一个重要的特性就是 ES6(ECMAScript 2015)中引入的箭头函数(Arrow Function)。箭头函数不仅…...
BiLSTM模型实现
# 本段代码构建类BiLSTM, 完成初始化和网络结构的搭建 # 总共3层: 词嵌入层, 双向LSTM层, 全连接线性层 # 本段代码构建类BiLSTM, 完成初始化和网络结构的搭建 # 总共3层: 词嵌入层, 双向LSTM层, 全连接线性层 import torch import torch.nn as nn# 本函数实现将中文文本映射为…...
linux内核源码学习所需基础
1.面向对象的思想,尤其是oopc的实现方式。 2.设计模式。 这两点需要内核源码学习者不仅要会c和汇编,还要接触一门面向对象的语言,比如c++/java/python等等任意一门都行,起码要了解面向对象的思想。 另外li…...
Java并发编程-AQS详解及案例实战(上篇)
文章目录 AQS概述AQS 的核心概念AQS 的工作原理AQS 的灵活性使用场景使用指南使用示例AQS的本质:为啥叫做异步队列同步器AQS的核心机制“异步队列”的含义“同步器”的含义总结加锁失败的时候如何借助AQS异步入队阻塞等待AQS的锁队列加锁失败时的处理流程异步入队的机制总结Ree…...
第11章 规划过程组(二)(11.8排列活动顺序)
第11章 规划过程组(二)11.8排列活动顺序,在第三版教材第391页; 文字图片音频方式 第一个知识点:主要输出 1、项目进度网络图 如图11-20 项目进度网络图示例 带有多个紧前活动的活动代表路径汇聚,而带有…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
