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 项目进度网络图示例 带有多个紧前活动的活动代表路径汇聚,而带有…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
《Docker》架构
文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器,docker,镜像,k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10pip3.10) 一:前言二:安装编译依赖二:安装Python3.10三:安装PIP3.10四:安装Paddlepaddle基础框架4.1…...
