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

后端开发刷题 | 没有重复项数字的全排列

描述

给出一组数字,返回该组数字的所有排列

例如:

[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
(以数字在数组中的位置靠前为优先级,按字典序排列输出。)

数据范围:数字个数 0<n≤6

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

示例1

输入:

[1,2,3]

返回值:

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例2

输入:

[1]

返回值:

[[1]]

思路分析:

经典的回溯算法问题——全排列(Permutations)

  • permute 方法:这是类的公共方法,接收一个整数数组 num 作为输入,并返回一个 ArrayList<ArrayList<Integer>> 类型的列表,其中每个内部列表代表 num 数组的一个排列。

    • 初始化一个 ArrayList<ArrayList<Integer>> 类型的 result 列表,用于存储所有排列。
    • 初始化一个 LinkedList<Integer> 类型的 list,用于在回溯过程中构建当前的排列。
    • 调用 backTrack 方法开始回溯过程。
  • backTrack 方法:这是一个私有方法,用于递归地生成所有排列。它接收三个参数:

    • num:原始整数数组。

    • list:当前正在构建的排列(以链表形式)。

    • result:用于存储所有排列的列表。

    • 递归终止条件:如果 list 的大小等于 num 的长度,说明已经构建了一个完整的排列,此时将这个排列(通过 new ArrayList<Integer>(list) 转换为不可变列表)添加到 result 中,并返回。

    • 递归过程:遍历 num 数组中的每个元素,如果当前元素已经存在于 list 中,则跳过该元素(避免重复排列)。否则,将该元素添加到 list 中,并递归调用 backTrack 方法继续构建下一个元素。递归返回后,需要撤销上一步的选择(即移除 list 中最后添加的元素),以便尝试其他可能的排列。

代码:

import java.util.*;public class Solution {public ArrayList<ArrayList<Integer>> permute(int[] num) {ArrayList<ArrayList<Integer>> result = new ArrayList<>();LinkedList<Integer> list = new LinkedList<>();backTrack(num, list, result);return result;}private void backTrack(int[] num, LinkedList<Integer> list,ArrayList<ArrayList<Integer>> result) {if (list.size() == num.length) {result.add(new ArrayList<Integer>(list));return;}for (int i = 0; i < num.length; i++) {if (list.contains(num[i])) {continue;}list.add(num[i]);backTrack(num, list, result);list.removeLast();}}
}

相关文章:

后端开发刷题 | 没有重复项数字的全排列

描述 给出一组数字&#xff0c;返回该组数字的所有排列 例如&#xff1a; [1,2,3]的所有排列如下 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1]. &#xff08;以数字在数组中的位置靠前为优先级&#xff0c;按字典序排列输出。&#xff09; 数据范围&#xff1a;数字…...

Python中的“打开与关闭文件”:从入门到精通

引言 在日常生活中&#xff0c;我们经常会遇到需要读取或保存信息的情况&#xff0c;比如记录笔记、保存配置信息或者处理大量的数据文件等。对于程序员来说&#xff0c;如何高效、安全地管理这些信息显得尤为重要。Python中的文件操作功能强大且易于使用&#xff0c;可以帮助…...

9.23 My_string.cpp

my_string.h #ifndef MY_STRING_H #define MY_STRING_H#include <iostream> #include <cstring>using namespace std;class My_string { private:char *ptr; //指向字符数组的指针int size; //字符串的最大容量int len; //字符串当前…...

【android10】【binder】【3.向servicemanager注册服务】

系列文章目录 可跳转到下面链接查看下表所有内容https://blog.csdn.net/handsomethefirst/article/details/138226266?spm1001.2014.3001.5501文章浏览阅读2次。系列文章大全https://blog.csdn.net/handsomethefirst/article/details/138226266?spm1001.2014.3001.5501 目录 …...

Java — LeetCode 面试经典150题(一)

双指针 125.验证回文串 题目 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后&#xff0c;短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。 字母和数字都属于字母数字字符。 给你一个字符串 s&#xff0c;如果它是 回文串 &#xff0c;返回…...

Python酷玩之旅_mysql-connector

前言 Python作为数据科学、机器学习等领域的必选武器&#xff0c;备受各界人士的喜爱。当你面对不同类型、存储于各类介质的数据时&#xff0c;第一时间是不是要让它亮个相&#xff1f;做个统计&#xff0c;画个图表&#xff0c;搞个报表… 等等。 正如Java中的JdbcDriver一样…...

7.搭建个人金融数据库之快速获取股票列表和基本信息!

前边我们提过&#xff0c;免费的数据一般来自于爬虫&#xff0c;获取难度和维护成本都比较高&#xff0c;其实不太适合小白用户。所以非必要情况下&#xff0c;我们尽量不用这种方式来获取数据。 我自己用的比较多的是tushare&#xff0c;一般来说有它也就够了&#xff0c;大…...

Nginx基础详解1(单体部署与集群部署、负载均衡、正反代理、nginx安装)

本阶段的任务 1.学会集群的操作概念 2.完成对Nginx的入门操作 3.使用Nginx实现集群和负载均衡 4.使用Nginx实现高可用的方案 目录 1.单体部署与集群部署 1.1单体部署的概念 1.2单体部署的优缺点 1.3集群部署的概念 1.4集群部署的优缺点 1.5集群部署需要注意的点 1.…...

等保一体机如何帮你应对网络攻击

等保一体机如何帮你应对网络攻击 在当今信息化时代&#xff0c;网络安全已成为企业和组织面临的重要挑战。随着网络攻击手段的不断升级&#xff0c;传统的安全防护措施已难以应对复杂多变的威胁。等保一体机作为一种集成化的安全防护解决方案&#xff0c;能够有效帮助企业应对…...

CVE-2024-1112 Resource Hacker 缓冲区溢出分析

漏洞简述 CVE-2024-1112 是 Resource Hacker 软件的一个缓冲区溢出漏洞。该漏洞存在于版本 3.6.0.92 中。由于软件在处理命令行中的文件路径时未对文件字符串长度进行限制&#xff0c;过长的字符串参数导致内存被过度写入&#xff0c;从而引发缓冲区溢出。 漏洞复现 构造长度…...

WebGL渲染与创建2D内容

目录 创建画布2D渲染修改顶点着色器光照深度测试混合模式WebGL是一个强大的工具,可以用来在Web浏览器中创建复杂的3D图形。虽然它的设计初衷是为了3D渲染,但也可以用于创建2D内容。通过巧妙地利用几何、投影和纹理,我们可以构建出各种2D图形。 创建画布 首先,我们需要在H…...

ArcGIS Desktop使用入门(三)图层右键工具——拓扑(下篇:地理数据库拓扑)

系列文章目录 ArcGIS Desktop使用入门&#xff08;一&#xff09;软件初认识 ArcGIS Desktop使用入门&#xff08;二&#xff09;常用工具条——标准工具 ArcGIS Desktop使用入门&#xff08;二&#xff09;常用工具条——编辑器 ArcGIS Desktop使用入门&#xff08;二&#x…...

LeetCode题练习与总结:二叉树的最近公共祖先--236

一、题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大&#xff08;一个节点也…...

uni-app 多环境配置

前后端分离模式下&#xff0c;不同的环境如开发环境&#xff08;dev&#xff09;、测试环境&#xff08;test&#xff09;、生产环境&#xff08;prod&#xff09;等&#xff0c;不同环境后端数据库、api地址等可能都不同 。 uni-app中只有development和production两个环境 以配…...

【d48】【Java】【力扣】LCR 123. 图书整理 I

思路 方法1&#xff1a;放进list,将list倒置&#xff0c;利用stream&#xff0c;将list改为int类型 方法2&#xff1a;递归&#xff1a;递归通用思路&#xff1b;明确每一层做什么确定返回值确定什么地方接收下层的返回值 每一层&#xff1a;调用下层&#xff0c;然后把自己…...

【MySQL】InnoDB 索引为什么使用B+树而不用跳表?

在MySQL中&#xff0c;为了加速查询&#xff0c;使用B树来构建索引&#xff0c;将查询性能从O(n)优化到O(log n)。虽然跳表同样提供O(log n)的查询效率并且实现相对简单&#xff0c;但B树更适合MySQL的索引使用&#xff0c;原因包括&#xff1a; B树和跳表的区别 B树和跳表的…...

【学习笔记】TLS/SSL握手之Records

TLS / SSL会话是由记录&#xff08;Records&#xff09;所组成&#xff0c;有4种records HandshakeAlertChange Cipher SpecApplication DataHandshake和Alert Records被分为子类型&#xff08;Subtypes&#xff09;&#xff1a; Handshake&#xff1a;Client HelloHandshake&a…...

【MySQL】创建新账号新数据库并授权

在 MySQL 中创建一个名为 new_user 的用户&#xff0c;并设置密码为 new_pass&#xff0c;然后创建一个名为 new_db 的数据库&#xff0c;并将该数据库的所有权限授予 new_user 用户。 登录 MySQL&#xff1a; mysql -u root -p创建用户&#xff1a; CREATE USER new_userlo…...

Nginx反向代理简介,作用及配置;Nginx负载均衡简介,作用及配置;

一&#xff0c;Nginx反向代理 1.1简介 反向代理服务器位于用户与目标服务器之间&#xff0c;但是对于用户而言&#xff0c;反向代理服务器就相当于目标服务器&#xff0c;即用户直接访问反向代理服务器就可以获得目标服务器的资源。同时&#xff0c;用户不需要知道目标服务器的…...

SAP MIGO M7146不支持移动原因

移动类型 Z91 查看配置&#xff1a;Z91 匹配的原因没有921 倒是Z92的原因里面有921 那解决方案有2种&#xff0c;但是要根据具体业务要求来 1、审视一下是否移动原因用错了 &#xff1f;换一个移动原因 2、确实是这个移动类型 要用到这个移动原因 &#xff0c;那就在上图 移…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...

基于江科大stm32屏幕驱动,实现OLED多级菜单(动画效果),结构体链表实现(独创源码)

引言 在嵌入式系统中&#xff0c;用户界面的设计往往直接影响到用户体验。本文将以STM32微控制器和OLED显示屏为例&#xff0c;介绍如何实现一个多级菜单系统。该系统支持用户通过按键导航菜单&#xff0c;执行相应操作&#xff0c;并提供平滑的滚动动画效果。 本文设计了一个…...

PH热榜 | 2025-06-08

1. Thiings 标语&#xff1a;一套超过1900个免费AI生成的3D图标集合 介绍&#xff1a;Thiings是一个不断扩展的免费AI生成3D图标库&#xff0c;目前已有超过1900个图标。你可以按照主题浏览&#xff0c;生成自己的图标&#xff0c;或者下载整个图标集。所有图标都可以在个人或…...

数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)

目录 &#x1f50d; 若用递归计算每一项&#xff0c;会发生什么&#xff1f; Horners Rule&#xff08;霍纳法则&#xff09; 第一步&#xff1a;我们从最原始的泰勒公式出发 第二步&#xff1a;从形式上重新观察展开式 &#x1f31f; 第三步&#xff1a;引出霍纳法则&…...