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

       📝个人主页:五敷有你      

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

⛺️稳中求进,晒太阳

题目

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

运行结果

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

(笔记)KEIL经常碰到的错误(持续整理)

KEIL常碰到的错误 一、ERROR报错1、Build时报错 Error: L6218E2、Build时报错 error 653、Default Compiler Version 54、core_cm3.h(1213): error: unknown type name inline 二、调试与仿真1、keil5软件仿真没有实时波形2、调试模式时&#xff0c;程序前没有灰块3、Periphera…

Python分组数据并保存到单独的文件中

当处理大型数据集时&#xff0c;通常需要将数据分组&#xff0c;并将每个分组的数据保存到单独的文件中。下面是一个使用 Python 中的 pandas 库来实现这一目标的示例代码。 步骤 1: 导入所需的库 import os import pandas as pd步骤 2: 读取 Excel 数据 # 读取 Excel 数据 …

关于Unity使用DLL的说法

最近在研究一些构建依赖相关的&#xff0c;特别是Unity在不同平台上使用第三方类库时候的问题。简单查了一下资料&#xff0c;其实不难理解&#xff0c;这里只是简单的记录一下&#xff0c;弄明白一个简单的道理就行了。 为什么有的第三方库(DoTween),NewtonSoft等的dll库&…

SF58-ASEMI适配器二极管SF58

编辑&#xff1a;ll SF58-ASEMI适配器二极管SF58 型号&#xff1a;SF58 品牌&#xff1a;ASEMI 封装&#xff1a;DO-27 最大平均正向电流&#xff08;IF&#xff09;&#xff1a;5A 最大循环峰值反向电压&#xff08;VRRM&#xff09;&#xff1a;600V 最大正向电压&…

根据状态转移图实现时序电路

描述 某同步时序电路的状态转换图如下&#xff0c;→上表示“C/Y”&#xff0c;圆圈内为现态&#xff0c;→指向次态。 请使用D触发器和必要的逻辑门实现此同步时序电路&#xff0c;用Verilog语言描述。 如图所示&#xff1a; 电路的接口如下图所示&#xff0c;C是单bit数据…

视频号小店好做吗?普通人没有货源,也可以做吗?

大家好&#xff0c;我是电商糖果 视频号小店作为2022年才出来的电商黑马项目&#xff0c;吸引了不少正在找创业项目的朋友。 这里面也有很多没有接触过电商&#xff0c;没有货源的普通人。 于是不少朋友就问糖果&#xff0c;如果普通人没有货源可以做吗&#xff1f;小店好做…

【回溯】Leetcode 51. N 皇后【困难】

N 皇后 按照国际象棋的规则&#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上&#xff0c;并且使皇后彼此之间不能相互攻击。 给你一个整数 n &#xff0c;返回所有不同的 n 皇后问题 的解决方案。…

CSS3 立体 3D 变换

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; 文章目录 ✍CSS3 立体 3D 变换&#x1f48e;1 坐标轴&#x1f48e;2 perspective 透视视…

cesium 平滑显示billboard 透明度

描述&#xff1a;加载billboard的时候&#xff0c;要么是显示&#xff0c;要么是隐藏&#xff0c;不能平滑的显示&#xff0c;有个从不显示到显示的过程 解决方案&#xff1a;创建billboard的时候给一个color&#xff0c;颜色为(255,255,255)&#xff0c;透明度从0-1 let opaci…

CSS设置内外边距

目录 内边距&#xff08;paddingj&#xff09;&#xff1a; 前言&#xff1a; 设置内边距&#xff1a; 外边距&#xff08;margin&#xff09;&#xff1a; 前言&#xff1a; 设置外边距&#xff1a; 补充(折叠)&#xff1a; 内边距&#xff08;padding&#xff09;&#…

设计模式-外观模式(Facade)

1. 概念 外观模式&#xff08;Facade Pattern&#xff09;是一种结构型设计模式&#xff0c;它提供了一个统一的接口&#xff0c;用于访问子系统中的一群接口。外观模式的主要目的是隐藏系统的复杂性&#xff0c;通过定义一个高层级的接口&#xff0c;使得子系统更容易被使用。…

秀米、135、蚂蚁编辑器如何为推文添加附件

秀米、135、蚂蚁编辑器作为第三方的公众号图文排版工具&#xff0c;给从事运营和编辑工作的同学提供了更多的排版选择。不同于公众号自家的编辑器&#xff0c;这些第三方编辑器脱离了微信的直接支持&#xff0c;在很多排版操作上&#xff0c;还是有很多操作不一样的地方。 公众…

UE C++ 学习

UBT&#xff08;虚幻编译工具&#xff08;UnrealBuildTool&#xff09;&#xff09;和UHT虚幻头工具&#xff08;UnrealHeaderTool&#xff09; UE有一组用于自动执行编译虚幻引擎过程的工具&#xff0c;包括 UBT和UHT&#xff08;以及其他工具&#xff09;。实现这一套工具的目…

R语言 多组堆砌图

目录 数据格式 普通绘图 添加比例 R语言 堆砌图_r语言堆砌图-CSDN博客 关键点在于数据转换步骤和数据比例计算步骤&#xff0c;然后个性化调整图。 ①data <- melt(dat, id.vars c("ID"))##根据分组变为长数据 ②#计算百分比## data2 <- ddply(data, …

Vue 3 中的哪些新特性对提升开发效率最有帮助?

Vue 3 引入了一系列新特性&#xff0c;旨在提升开发效率和改善开发体验。以下是一些对提升开发效率最有帮助的特性&#xff1a; Composition API: Composition API 允许开发者更灵活地组织代码&#xff0c;使得逻辑复用和维护变得更加容易。通过将相关功能的代码组织在一起&…

【Leetcode】2923. 找到冠军 I

文章目录 题目思路代码复杂度分析时间复杂度空间复杂度 结果总结 题目 题目链接&#x1f517; 一场比赛中共有 n n n 支队伍&#xff0c;按从 0 0 0 到 n − 1 n - 1 n−1 编号。 给你一个下标从 0 0 0 开始、大小为 n ∗ n n * n n∗n 的二维布尔矩阵 g r i d grid gr…

【cmake安装】研发环境搭建之cmake安装

背景 因为项目需求&#xff0c;需要家里的Win10 PC安装Ubuntu 20.04虚拟机并搭建编译环境&#xff0c;需要安装cmake编译环境 直接命令安装即可 sudo apt install cmake安装成功后&#xff1a; 3.16版本暂时也够用了

院子里种点什么树风水好呢?

植物本身是一个丰富的生活领域&#xff0c;有着强烈的视觉暗示。其实&#xff0c;在家中养植物&#xff0c;是有许多好处的&#xff0c;它不仅能够装点庭院的环境让家更美丽&#xff0c;还能调节室内的空气质量&#xff0c;对家人的运势也有着非常大的帮助。 不过&#xff0c;并…

向量数据库Chroma学习记录

一 简介 Chroma是一款AI开源向量数据库&#xff0c;用于快速构建基于LLM的应用&#xff0c;支持Python和Javascript语言。具备轻量化、快速安装等特点&#xff0c;可与Langchain、LlamaIndex等知名LLM框架组合使用。 二 基本用法 1 安装 安装方式非常简单&#xff0c;只需…

公司能监控员工电脑屏幕吗

公司能监控员工电脑屏幕吗&#xff1f; 当然可以&#xff01; 公司需要在工作时间去监控员工电脑的。 电脑属于公司财产&#xff0c;公司对于员工在工作期间的上网行为有监控的权利和职责&#xff0c;可以监控员工在工作期间的信息交流&#xff0c;并且对他们的上网行为进行…