【回溯】Leetcode 77. 组合【中等】
组合
- 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
解题思路
- 定义递归函数:定义一个递归函数 backtrack 用来生成组合。
- 递归终止条件:如果当前组合的长度达到 k,将其添加到结果列表中。
- 选择元素:从当前起始元素到 n 进行迭代,选择每个元素加入当前组合。
- 递归调用:选择元素后,递归调用函数生成下一个元素的组合。
- 回溯:在递归完成后,移除当前选择的元素,尝试选择下一个元素。
Java实现
public class Combine {public List<List<Integer>> combine(int n, int k) {List<List<Integer>> res = new ArrayList<>();backtrack(1, n, k, new ArrayList<>(), res);return res;}private void backtrack(int start, int n, int k, List<Integer> path, List<List<Integer>> res) {// 如果组合完成if (path.size() == k) {res.add(new ArrayList<>(path));return;}// 从`start`到`n`遍历所有的数字for (int i = start; i <= n; i++) {// 将`i`添加到当前组合path.add(i);// 使用下一个整数完成组合backtrack(i + 1, n, k, path, res);// 回溯,通过移除`i`path.remove(path.size() - 1);}}// 测试用例public static void main(String[] args) {Combine solution = new Combine();System.out.println(solution.combine(4, 2)); // 期望输出: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]System.out.println(solution.combine(5, 3)); // 期望输出: [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]}
}
时间空间复杂度
- 时间复杂度:O(C(n, k) * k),其中 C(n, k) 是从 n 个数中选 k 个数的组合数。生成每个组合需要 O(k) 的时间。
- 空间复杂度:O(k),递归栈的深度最多为 k,存储当前组合的路径 path 也需要 O(k) 的空间。
相关文章:
【回溯】Leetcode 77. 组合【中等】
组合 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1: 输入: n 4, k 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 解题思路 定义递归函数࿱…...
项目中常量的定义方式
方式一 在常量个数少的时候,通常情况下使用这种方式。 public class MqConstants {public static final String EXCHANGE_1 "exchange1";public static final String EXCHANGE_2 "exchange2";public static final String EXCHANGE_3 "…...
BL104钡铼多协议采集网关助力企业智能化转型
BL104钡铼多协议采集网关(PLC物联网关BL104)是为满足工业环境需求而设计的专业工业级协议转换网关。它在企业智能化转型过程中扮演着关键角色,为企业提供了高效、稳定的通信解决方案,助力企业实现智能化转型。 首先,P…...
【LC刷题】DAY08:151 55 28 459
【LC刷题】DAY08:151 55 28 459 文章目录 【LC刷题】DAY08:151 55 28 459151. 反转字符串中的单词 [link](https://leetcode.cn/problems/reverse-words-in-a-string/description/)55. 右旋字符串 [link](https://kamacoder.com/problempage.php?pid106…...
Debian 12.5 一键安装 Oracle 19C 单机
前言 Oracle 一键安装脚本,演示华为 Debian 12.5 一键安装 Oracle 19C 单机版过程(全程无需人工干预)。 ⭐️ 脚本下载地址:Shell脚本安装Oracle数据库 安装准备 1、安装好操作系统,建议安装图形化2、配置好网络3、上…...
ARP协议相关
把ip地址解析成mac地址这里的mac地址就是路由器的mac地址 免费ARP 源ip和目的ip都是一样的,那怎么让其他人更新arp表呢?? 是因为目标mac是全f,是一个广播报文 如果冲突就是ip一样但是mac又不一样 代理ARP pc1和pc4是在同一个子网…...
Github 2024-06-14 开源项目日报Top10
根据Github Trendings的统计,今日(2024-06-14统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量JavaScript项目2Python项目2非开发语言项目2TypeScript项目1Dart项目1Rust项目1Lua项目1Java项目1Jupyter Notebook项目1从零开始构建你喜爱的技…...
记录AE快捷键(持续补充中。。。)
记录AE快捷键 快捷键常用快捷键图层快捷键工具栏图层与属性常用指令视图菜单时间轴常规快捷键项目首选项功能摄像机操作 常用操作导入AI/PS工程文件加选一个关键参数快速回到上下一帧隐藏/显示图层关键帧拉长缩短关键帧按着鼠标左键不松手,在秒表那一列往下移动会都…...
基于springboot实现问卷调查系统项目【项目源码+论文说明】计算机毕业设计
基于springboot实现问卷调查系统演示 摘要 传统信息的管理大部分依赖于管理人员的手工登记与管理,然而,随着近些年信息技术的迅猛发展,让许多比较老套的信息管理模式进行了更新迭代,问卷信息因为其管理内容繁杂,管理数…...
React@16.x(29)useRef
目录 1,介绍2,和 React.createRef() 的区别3,计时器的问题 目前来说,因为函数组件每次触发更新时,都会重新运行。无法像类组件一样让一些内容保持不变。 所以才出现了各种 HOOK 函数:useState,u…...
无人机的力量——在民用方面的应用
无人机在民用方面的应用广泛且多样化,以下是对其应用的详细介绍: 影视航拍: 无人机航拍影像具有高清晰、大比例尺、小面积、高视角的优点,特别适合获取带状地区航拍影像(如公路、铁路、河流、水库、海岸线等ÿ…...
探索档案未来,尽在ARCHE-2024
2024年第三届上海国际智慧档案展览会暨高峰论坛(ARCHE-2024)将于2024年6月19日至21日在上海跨国采购会展中心隆重举行。深圳市铨顺宏科技有限公司应邀参展,将以全新形象盛装亮相,展示其在档案管理领域的最新技术和解决方案。 ARC…...
Maven 核心插件 maven-clean-plugin 使用详解
在软件开发中,构建和管理项目的复杂性随着代码量和依赖的增加而不断提升。Maven作为一个强大的构建工具,简化了这一过程,并通过其插件机制提供了丰富的功能。其中,maven-clean-plugin 是Maven的核心插件之一,它在项目的…...
金融数据中心布线运维管理解决方案
金融行业的核心业务,如交易、支付、结算等,对网络的依赖程度极高。布线作为网络基础设施的重要组成部分,其稳定性和可靠性直接关系到业务的连续运行。因此,良好的布线管理能够确保网络系统的稳定运行,减少因网络故障导…...
C++初学者指南第一步---2. Hello world
C初学者指南第一步—2. Hello world 目录 C初学者指南第一步---2. Hello world1.源文件 “Hello.cpp”2.编译hello.cpp3.术语4.编译器标志5.不要使用 “using namespace std;” ! 1.源文件 “Hello.cpp” #include <iostream> // our first program int main…...
gitLab批量下载有权限的项目
前言 参考 https://www.jianshu.com/p/b3d4e5cee835 适用于git私服拉取个人所涉及权限的代码,方便有多个项目权限的人快速拉取自己所有权限的代码。 默认生成目录结构与gitlab一致 步骤一:获取权限你的代码权限文件d 从gitlab私服生成所有你有权限的代码信息 …...
解决 kali 中使用 vulhub 拉取不到镜像问题
由于默认情况下,访问的镜像是国外的,而从 2023 年开始,docker 的镜像网站就一直访问不了,所以我们可以把镜像地址改成国内的阿里云镜像地址。 1、在 cd /etc/docker/目录下创建或修改daemon.json文件 sudo touch daemon.json 2、在…...
CSS3 简介
CSS3 简介 CSS3,即层叠样式表的第三代,是网页设计和开发中不可或缺的技术之一。它为HTML元素提供了更加丰富和灵活的样式定义,使得网页不仅结构清晰,而且外观精美、交互性强。CSS3继承了CSS2的基本特性,并引入了许多新…...
springboot事务管理的机制是什么
SpringBoot的事务管理机制实质上是基于Spring框架的事务处理机制。其主要目的是确保一系列数据库操作要么全部成功,要么全部失败(回滚),从而维护数据的完整性和一致性。 SpringBoot事务管理遵循ACID四大特性: 1、原子…...
Linux下tar命令解压缩
tar 命令是 Unix 和 Linux 系统中用来创建归档文件以及提取归档文件的工具。它通常用于备份文件或将多个文件和目录打包成一个单独的归档文件。默认情况下,tar 不会对文件进行压缩,但可以通过结合其他压缩工具(如 gzip 或 bzip2)来…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
