当前位置: 首页 > news >正文

力扣日记2.21-【回溯算法篇】46. 全排列

力扣日记:【回溯算法篇】46. 全排列

日期:2023.2.21
参考:代码随想录、力扣

46. 全排列

题目描述

难度:中等

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2:

输入:nums = [0,1]
输出:[[0,1],[1,0]]

示例 3:

输入:nums = [1]
输出:[[1]]

提示:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

题解

cpp ver
class Solution {
public:vector<int> path;vector<vector<int>> result;int used[21] = {0}; // 记录哪些值取过vector<vector<int>> permute(vector<int>& nums) {backtracking(nums);return result;}void backtracking(vector<int>& nums) {// 终止条件if (path.size() == nums.size()) {result.push_back(path);return;}// for 横向遍历for (int i = 0; i < nums.size(); i++) {// 需要标记哪些值已经取过了, nums[i] [-10, 10] -> [0, 20] if (used[nums[i] + 10] == 1) continue;  // 取过了,则跳过该值// 否则,标记取过,并进行取值与递归used[nums[i] + 10] = 1;path.push_back(nums[i]);backtracking(nums);path.pop_back();used[nums[i] + 10] = 0;}}
};

复杂度

时间复杂度: O(n!)
空间复杂度: O(n)

第一个取值有n个选择,第二个有(n-1)个选择(除去第一个),以此类推,总共 n*(n-1)*…*1=n!种情况

思路总结

  • 全排列本质上也是组合问题,其特点是:
    • 全:要求需要取到集合所有值才行(到了叶子节点才能放入result)
    • 排列:则说明相同值但不同排序得到的组合是不同,这样则要求,在每次for循环时都需要从最前面开始遍历(不需要之前组合和子集问题的startindex),但这样需要考虑避免在纵向递归取到重复的值,即要做到在for循环遍历时,只有未取过的值才进行取值遍历
  • 关键是通过一个 used 数组(哈希表)记录取过的值,即在for循环每次取值前,判断当前值在 used中是否为1,如果为1说明取过,则跳过,否则进行取值遍历和回溯。且每次取值后在used记录该值已取(对应地,要在回溯时置0)。
  • 树状结构示意图(from代码随想录)
    • 在这里插入图片描述
  • 注:used也可以用以下表示:
    vector<bool> used(nums.size(), false);
    // 每次for循环取值后
    used[i] == true;	// i 为for循环索引(与nums[i]同)
    

相关文章:

力扣日记2.21-【回溯算法篇】46. 全排列

力扣日记&#xff1a;【回溯算法篇】46. 全排列 日期&#xff1a;2023.2.21 参考&#xff1a;代码随想录、力扣 46. 全排列 题目描述 难度&#xff1a;中等 给定一个不含重复数字的数组 nums &#xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1&…...

[AIGC] Kafka 消费者的实现原理

在 Kafka 中&#xff0c;消费者通过订阅主题来消费数据。每个消费者都属于一个消费者组&#xff0c;消费者组中的多个消费者可以共同消费一个主题&#xff0c;实现分布式消费。每个消费者都会维护自己的偏移量&#xff0c;用于记录已经读取到的消息位置。消费者可以选择手动提交…...

Dubbo框架admin搭建

Dubbo服务监控平台&#xff0c;dubbo-admin是图形化的服务管理界面&#xff0c;从服务注册中心获取所有的提供者和消费者的配置。 dubbo-admin是前后端分离的项目&#xff0c;前端使用Vue&#xff0c;后端使用springboot。因此&#xff0c;前端需要nodejs环境&#xff0c;后端需…...

Linux 内存top命令详解

通过top命令可以监控当前机器的内存实时使用情况&#xff0c;该命令的参数解释如下&#xff1a; 第一行 15:30:14 —— 当前系统时间 up 1167 days, 5:02 —— 系统已经运行的时长&#xff0c;格式为时:分 1 users ——当前有1个用户登录系统 load average: 0.00, 0.01, 0.05…...

OCP使用CLI创建和构建应用

文章目录 环境登录创建project赋予查看权限部署第一个image创建route检查pod扩展应用 部署一个Python应用连接数据库创建secret加载数据并显示国家公园地图 清理参考 环境 RHEL 9.3Red Hat OpenShift Local 2.32 登录 通过 crc console --credentials 可以查看登录信息&…...

Chrome关闭时出现弹窗runtime error c++R6052,且无法关闭

环境&#xff1a; Chrome 版本121 Win10专业版 问题描述&#xff1a; Chrome关闭时出现弹窗runtime error cR6052&#xff0c;且无法关闭 解决方案&#xff1a; 1.任务管理器打开&#xff0c;强制结束进程 2.再次打开谷歌浏览器&#xff0c;打开设置关于Chrome&#xff0…...

【动态规划专栏】专题二:路径问题--------6.地下城游戏

本专栏内容为&#xff1a;算法学习专栏&#xff0c;分为优选算法专栏&#xff0c;贪心算法专栏&#xff0c;动态规划专栏以及递归&#xff0c;搜索与回溯算法专栏四部分。 通过本专栏的深入学习&#xff0c;你可以了解并掌握算法。 &#x1f493;博主csdn个人主页&#xff1a;小…...

flink operator 1.7 更换日志框架log4j 到logback

更换日志框架 flink 1.18 1 消除基础flink框架log4j 添加logback jar 1-1 log4j log4j-1.2-api-2.17.1.jar log4j-api-2.17.1.jar log4j-core-2.17.1.jar log4j-slf4j-impl-2.17.1.jar 1-2 logback logback-core-1.2.3.jar logback-classic-1.2.3.jar slf4j-api-1.7.25.jar2 …...

算法项目(1)—— LSTM+CNN+四种注意力对比的股票预测

本文包含什么? 项目运行的方式(包教会)项目代码(在线运行免环境配置)不通注意力的模型指标对比一些效果图运行有问题? csdn上后台随时售后.项目说明 本项目实现了基于CNN+LSTM构建模型,然后对比不同的注意力机制预测股票走势的效果。首先看一下模型结果的对比: 模型MS…...

Qt C++春晚刘谦魔术约瑟夫环问题的模拟程序

什么是约瑟夫环问题&#xff1f; 约瑟夫问题是个有名的问题&#xff1a;N个人围成一圈&#xff0c;从第一个开始报数&#xff0c;第M个将被杀掉&#xff0c;最后剩下一个&#xff0c;其余人都将被杀掉。例如N6&#xff0c;M5&#xff0c;被杀掉的顺序是&#xff1a;5&#xff…...

Typora+PicGO+腾讯云COS做图床

文章目录 Typora&#xff0b;PicGO&#xff0b;腾讯云COS做图床一、为什么使用图床二、Typora、PicGO和腾讯云COS介绍三、下载Typora和PicGOTyporaPicGO 四、配置Typora、PicGO和腾讯云COS腾讯云COS配置PicGO配置Typora配置 Typora&#xff0b;PicGO&#xff0b;腾讯云COS做图床…...

WebStorm | 如何修改webstorm中新建html文件默认生成模板中title的初始值

在近期的JS的学习中&#xff0c;使用webstorm&#xff0c;总是要先新建一个html文件&#xff0c;然后再到里面书写<script>标签&#xff0c;真是麻烦&#xff0c;而且标题也是默认的title&#xff0c;想改成文件名还总是需要手动去改 经过小小的研究&#xff0c;找到了修…...

大厂的数据质量中心系统设计

日常工作中&#xff0c;数据开发上线完一个任务后并不是就可以高枕无忧&#xff0c;时常因上游链路数据异常或者自身处理逻辑的 BUG 导致产出的数据结果不可信。而问题发现可经历较长周期&#xff08;尤其离线场景&#xff09;&#xff0c;往往是业务方通过上层数据报表发现数据…...

docker (一)-简介

1.什么是docker Docker 是一个开源的应用容器引擎&#xff0c;由于docker影响巨大&#xff0c;今天也用"Docker" 指代容器化技术。 2.docker的优势 一键部署&#xff0c;开箱即用 容器使用基于image镜像的部署模式&#xff0c;image中包含了运行应用程序所需的一…...

全国乙卷高考理科数学近年真题的选择题练一练和解析

虽然很多中小学才陆陆续续开学&#xff0c;但是高三的学子们一定是过年的时候也在抓紧备考&#xff0c;毕竟&#xff0c;距离2024年高考只剩下不到四个月了。 如何在最后四个月的时间提高成绩&#xff1f;以高考真题为抓手是一个不错的方法&#xff0c;因为真题都是严格遵循考试…...

uniapp运动课程健身打卡系统微信小程序

考虑到实际生活中在我来运动管理方面的需要以及对该系统认真的分析,将系统分为小程序端模块和后台管理员模块&#xff0c;权限按管理员和用户这两类涉及用户划分。 (a) 管理员&#xff1b;管理员使用本系统涉到的功能主要有&#xff1a;首页、个人中心、用户管理、课程类别管理…...

IP详细地理位置查询:技术原理与应用实践

IP地址是互联网上设备的唯一标识&#xff0c;在网络安全、个性化服务等领域具有重要意义。通过IP详细地理位置查询&#xff0c;可以获取到IP地址所在地的具体信息&#xff0c;为网络管理、定位服务等提供支持。IP数据云将深入探讨IP详细地理位置查询的技术原理、应用实践以及相…...

SpringBoot2整合支付宝进行沙箱支付

目录 1. 进入支付宝的开放平台 2. 导入Maven依赖 3. 配置application.yml文件 NATAPP.cn(内网穿透工具) 注册登录 下载 4. 后端配置 5. 测试 1. 进入支付宝的开放平台 开发平台: 支付宝开放平台 登录后,点击控制台 点击最下面的沙箱 2. 导入Maven依赖 <dependency…...

世界顶级名校计算机专业,都在用哪些书当教材?

清华、北大、MIT、CMU、斯坦福的学霸们在新学期里要学什么&#xff1f;今天我们来盘点一下那些世界名校计算机专业采用的教材。 欢迎来到英杰社区&#xff1a; https://bbs.csdn.net/topics/617804998 欢迎来到阿Q社区&#xff1a; https://bbs.csdn.net/topics/617897397 &…...

Linux内核解读

来自鹅厂架构师 作者&#xff1a;aurelianliu 工作过程中遇到的调度、内存、文件、网络等可以参考。 1.os运行态 X86架构&#xff0c;用户态运行在ring3&#xff0c;内核态运行在ring0&#xff0c;两个特权等级。 &#xff08;1&#xff09;内核、一些特权指令&#xff0c;例…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...