【算法分析与设计】全排列

       📝个人主页:五敷有你      

 🔥系列专栏:算法分析与设计

⛺️稳中求进,晒太阳

题目

        给定一个不含重复数字的整数数组 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]]

思路

  • 回溯

这个问题可以看作是n个排列成一行的空格,我们需要从左向右填入给定的n个数,每个只能使用一次,那么很直接的可以想到穷举法,从左向右依次填入,看能不能填完这个n个空格,在这个过程可以使用回溯来模拟。

我们定义一个backtrack(first,output)表示从左向右填到first个位置,当前排列为output,那么整个递归函数分为两个情况:

一、first==n 

这个情况就表示已经填完了n个位置,可以进行一次排列的收集

二、first<n

这个情况是从第一个格到first是固定了,之后就

之后first左边的固定了,右边的还在回溯。

first现在指向2,之后2和2自己进行交换,有人可能回想为什么2还要与自己进行交换,因为1 2 3 4 5 6 本身也是一种排列,难道不是吗?呼

然后first指向3,同理,自身与自身交换一次,然后一直回溯,。。。。

之后再回来回溯交换

     for (int i = first; i < n; i++) {// 动态维护数组Collections.swap(output, first, i);// 继续递归填下一个数backtrack(n, output, res, first + 1);// 撤销操作Collections.swap(output, first, i);}

代码实现:

class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> res = new ArrayList<List<Integer>>();List<Integer> output = new ArrayList<Integer>();for (int num : nums) {output.add(num);}int n = nums.length;backtrack(n, output, res, 0);return res;}public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {// 所有数都填完了if (first == n) {res.add(new ArrayList<Integer>(output));}for (int i = first; i < n; i++) {// 动态维护数组Collections.swap(output, first, i);// 继续递归填下一个数backtrack(n, output, res, first + 1);// 撤销操作Collections.swap(output, first, i);}}
}

运行结果

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

单细胞RNA测序(scRNA-seq)Cellranger流程入门和数据质控

单细胞RNA测序(scRNA-seq)Cellranger流程入门和数据质控 单细胞RNA测序(scRNA-seq)基础知识可查看以下文章: 单细胞RNA测序(scRNA-seq)工作流程入门 单细胞RNA测序(scRNA-seq)细胞分离与扩增 1. 单细胞RNA-seq样本数据说明 样本数据来源文章:Acquired cancer re…

探秘大模型:《提示工程:技巧、方法与行业应用》背后的故事

提示工程是一种新兴的利用人工智能的技术&#xff0c;它通过设计提示引导生成式 AI 模型产生预期的输出&#xff0c;来提升人与 AI 的互动质量&#xff0c;激发 AI 模型的潜力&#xff0c;提升AI的应用水平。 为了让每一个人都拥有驱动大模型的能力&#xff0c;以微软全球副总裁…

Acwing.3999 最大公约数(gcd欧拉函数)

题解 给定两个正整数 a,m&#xff0c;其中 a<m。 请你计算&#xff0c;有多少个小于 m 的非负整数 x满足&#xff1a; gcd(a,m)gcd(ax,m) 输入格式 第一行包含整数 T &#xff0c;表示共有 T 组测试数据。 每组数据占一行&#xff0c;包含两个整数 a,m 。 输出格式 每…

计算机网络——40各个层次的安全性

各个层次的安全性 安全电子邮件 Alice需要发送机密的报文m给Bob Alice 产生随机的对称秘钥&#xff0c; K s K_s Ks​使用 K s K_s Ks​对报文进行加密&#xff08;为了效率&#xff09;对 K s K_s Ks​使用Bob的公钥进行加密发送 K s ( m ) K_s(m) Ks​(m)和 K B ( K S ) K…

Linux执行命令监控详细实现原理和使用教程,以及相关工具的使用

Linux执行命令监控详细实现原理和使用教程&#xff0c;以及相关工具的使用。 0x00 背景介绍 Linux上的HIDS需要实时对执行的命令进行监控&#xff0c;分析异常或入侵行为&#xff0c;有助于安全事件的发现和预防。为了获取执行命令&#xff0c;大致有如下方法&#xff1a; 遍…

别等Sora了!字节跳动旗下国产AI工具Dreamina,AI视频生成虽不完美,但够惊艳!

别等 Sora 了&#xff0c;试试字节跳动的 Dreamina&#xff01;Dreamina 是剪映旗下的一个 AI 创作平台&#xff0c;目前支持「文生图」、「智能画布」和「视频生成」功能。 Dreamina 官网&#xff1a;https://dreamina.jianying.com/ai-tool/home 之前对 Dreamina 的「文生图…

暴力枚举法

虽然暴力枚举法有时候效率低&#xff0c;时间复杂度高&#xff0c;但是在面对小规模数据集的时候&#xff0c;暴力枚举法往往是很好的思维利器。 B: 01 串的熵&#xff08;5分&#xff09; 问题描述 #include <iostream> #include <cmath> #include <algorithm…

【C++算法模板】数论:欧拉筛,线性查找质数的算法

文章目录 1&#xff09;传统找质数的方法&#xff08;优化筛选次数&#xff09;2&#xff09;欧拉筛 1&#xff09;传统找质数的方法&#xff08;优化筛选次数&#xff09; bool isPrime(int num) {for(int i2;i<sqrt(num)) {if(num%i0)return false;}return true; }如果要…

Training - 使用 WandB 配置 可视化 模型训练参数

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://blog.csdn.net/caroline_wendy/article/details/137529140 WandB (Weights&Biases) 是轻量级的在线模型训练可视化工具&#xff0c;类似于 TensorBoard&#xff0c;可以帮助用户跟踪…

统信UOS(Linux)安装nvm node管理工具

整篇看完再操作&#xff0c;有坑&#xff01;&#xff01; 官网 nvm官网 按照官网方式安装&#xff0c;一直报 错 经过不断研究&#xff0c;正确步骤如下 1、下载安装包 可能因为网络安全不能访问github&#xff0c;我是链接热点下载的 wget https://github.com/nvm-sh/…

three.js跟着教程实现VR效果(四)

参照教程&#xff1a;https://juejin.cn/post/6973865268426571784&#xff08;作者&#xff1a;大帅老猿&#xff09; 1.WebGD3D引擎 用three.js &#xff08;1&#xff09;使用立方体6面图 camera放到 立方体的中间 like “回” 让贴图向内翻转 &#xff08;2&#xff09;使…

界面控件DevExpress WinForms/WPF v23.2 - 富文本编辑器支持内容控件

众所周知内容控件是交互式UI元素(文本字段、下拉列表、日期选择器)&#xff0c;用于在屏幕上输入和管理信息。内容控件通常在模板/表单中使用&#xff0c;以标准化文档格式和简化数据输入。DevExpress文字处理产品库&#xff08;Word Processing Document API、WinForm和WPF富文…

科研学习|可视化——Origin绘制相关性系数矩阵

一、Origin软件版本 Origin2021版本 二、插件下载地址 CorrelationPlot.opx资源-CSDN文库 三、插件安装步骤 从上述链接下载插件将插件解压缩&#xff08;最好是解压缩到orgin的安装目录&#xff09;用origin打开插件&#xff08;或者打开origin&#xff0c;将插件拖拽到origin…

【一招鲜】-阿里云服务器安全更新 RHSA-2021:3889: java-1.8.0-openjdk 安全和BUG修复更新

形似这种&#xff1a; RHSA-2021:3889: java-1.8.0-openjdk 安全和BUG修复更新 #1 查看可更新的软件java yum list updates |grep java #2 如果有可更新软件&#xff0c;则进行更新 yum -y update java-1.8.0-openjdk.x86_64 形似这种&#xff1a; RHSA-2021:4782: openssh …

C++设计模式:原型模式(八)

1、定义与动机 定义&#xff1a;使用原型实例指定创建对象的种类&#xff0c;然后通过拷贝这些原型来创建新的对象。 动机&#xff1a; 在软件系统中&#xff0c;经常面临着“某些结构复杂的对象”的创建工作&#xff1b;由于需求的变化&#xff0c;这些对象经常面临着剧烈的变…

CSS基础+基本选择器和复合选择器(如果想知道CSS的基础+基本选择器和复合选择器知识点,那么只看这一篇就足够了!)

前言&#xff1a;在我们学习完了html之后&#xff0c;我们就要开始学习三大件中的第二件—CSS&#xff0c;CSS 可以控制多重网页的样式和布局&#xff0c;也就是将我们写好的html代码加上一层华丽的衣裳&#xff0c;使网页变得更加精美。 ✨✨✨这里是秋刀鱼不做梦的BLOG ✨✨✨…

实时多目图像拼接算法

实时多目图像拼接算法可以用于将多个视角的图像拼接成一个全景图像或者视频。 以下是一种常见的实时多目图像拼接算法的基本实现步骤: 特征提取与匹配: 对于每个输入图像,使用特征提取算法(如SIFT、ORB等)来提取图像中的特征点。然后,使用特征描述符(如ORB描述符)来描述…

Docker 学习笔记(六):挑战容器数据卷技术一文通,实战多个 MySQL 数据同步,能懂会用,初学必备

一、前言 记录时间 [2024-4-11] 系列文章简摘&#xff1a; Docker学习笔记&#xff08;二&#xff09;&#xff1a;在Linux中部署Docker&#xff08;Centos7下安装docker、环境配置&#xff0c;以及镜像简单使用&#xff09; Docker 学习笔记&#xff08;三&#xff09;&#x…

vue3 +Taro 页面实现scroll-view 分页功能

需求 现在分页列表 后端只给你一个分页的数据列表 没有总页数 没有当前的分页 页数 只有这么一个list 、、、 如何去分页 我这使用的是scroll-view 组件 滑动到底部的事件 根据你当前设定的每页的数据数量和后端返回给你的数据列表数量 当某一次分页 两个数量不相等了以后 就…

1.汉诺塔问题

C力扣 汉诺塔 class Solution { public:void hanota(vector<int>& a, vector<int>& b, vector<int>& c) {dfs(a,b,c,a.size());}void dfs(vector<int>& a, vector<int>& b, vector<int>& c,int n){if(n1){c.push…