python-leetcode 54.全排列

devtools/2025/3/18 12:22:51/

题目:

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

 回溯法

一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解(或者至少不是最后一个解),回溯算法会通过在上一步进行一些变化抛弃该解,即回溯并且再次尝试。

方法一:回溯

有 n 个排列成一行的空格,从左往右依此填入题目给定的 n 个数,每个数只能使用一次。以想到一种穷举的算法,即从左往右每一个位置都依此尝试填入一个数,看能不能填完这 n 个空格,在程序中用「回溯法」来模拟这个过程。

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

如果 first=n,说明已经填完了 n 个位置(注意下标从 0 开始),找到了一个可行的解将 output 放入答案数组中,递归结束

如果 first<n,要考虑这第 first 个位置要填哪个数。根据题目要求不能填已经填过的数,因此很容易想到的一个处理手段是定义一个标记数组 vis 来标记已经填过的数,那么在填第 first 个数的时候遍历题目给定的 n 个数,如果这个数没有被标记过,就尝试填入,并将其标记,继续尝试填下一个位置,即调用函数 backtrack(first+1,output)。回溯的时候要撤销这一个位置填的数以及标记,并继续尝试其他没被标记过的数。

使用标记数组来处理填过的数是一个很直观的思路,但是可不可以去掉这个标记数组呢?毕竟标记数组也增加了算法的空间复杂度。

答案是可以的,可以将题目给定的 n 个数的数组 nums 划分成左右两个部分,左边的表示已经填过的数,右边表示待填的数,在回溯的时候动态维护这个数组即可。

具体来说,假设已经填到第 first 个位置,那么 nums 数组中 [0,first−1] 是已填过的数的集合,[first,n−1] 是待填的数的集合,尝试用 [first,n−1] 里的数去填第 first 个数,假设待填的数的下标为 i,么填完以后将第 i 个数和第 first 个数交换,即能使得在填第 first+1 个数的时候 nums 数组的 [0,first] 部分为已填过的数,[first+1,n−1] 为待填的数,回溯的时候交换回来即能完成撤销操作。

举个简单的例子,假设有 [2,5,8,9,10] 这 5 个数要填入,已经填到第 3 个位置,已经填了 [8,9] 两个数,那么这个数组目前为 [8,9 ∣ 2,5,10] 这样的状态,分隔符区分了左右两个部分。假设这个位置要填 10 这个数,为了维护数组,我们将 2 和 10 交换,即能使得数组继续保持分隔符左边的数已经填过,右边的待填 [8,9,10 ∣ 2,5] 。

输入:nums = [1, 2, 3]
目标:生成所有可能的排列。

class Solution(object):def permute(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""def backtrack(first=0):  #定义回溯函数用于递归生成所有排列,first 代表当前正在填充的索引位置,默认从 0 开始,该函数的目标是通过交换 nums 中的元素,生成所有可能的排列if first==n:  #说明 nums 的排列已经完成res.append(nums[:])#nums 的拷贝(不能直接 append(nums),否则后续的修改会影响结果)for i in range(first,n):#遍历索引 first 到 n-1 之间的所有元素nums[first],nums[i]=nums[i],nums[first]#将 nums[i] 交换到 first 位置,使其成为当前排列的第 first 个数backtrack(first+1)#填充下一个位置的数nums[first],nums[i]=nums[i],nums[first]#nums是原地修改的,在回溯后需要撤销之前的交换,恢复数组原状,避免影响其他排列的生成n=len(nums)res=[]backtrack()return res

时间复杂度:O(n×n!),其中 n 为序列的长度

空间复杂度:O(n),其 n 为序列的长度。除答案数组以外,递归函数在递归过程中需要为每一层递归函数分配栈空间,

源自力扣官方题解
 


http://www.ppmy.cn/devtools/168054.html

相关文章

基于 YOLOv8 和 PyQt5 的火焰、烟雾检测

目标检测是计算机视觉领域的一个重要研究方向,广泛应用于安防监控、自动驾驶、工业检测等领域。近年来,随着深度学习技术的快速发展,YOLO(You Only Look Once)系列算法因其速度快、精度高而备受关注。本文将介绍如何利用 YOLOv8 和 PyQt5 开发一个视频目标检测应用,实现从…

Rust学习之实现命令行小工具minigrep(一)

Rust学习之实现命令行小工具minigrep&#xff08;一&#xff09; 通过开发一个在指定文件中查询某个特定字符串命的令行小工具进一步学习和巩固Rust基础。 已同步自建博客地址 源码已上传Github 创建项目 cargo new minigrep1接收命令行参数 我们想要实现的命令效果如下&…

CMake 开发库(Library)的最佳实践

1. 使用 Modern CMake 开发库 CMake 在 C社区中非常流行, 可以说是事实上的 C 包管理工具. 在Meeting C 开发者调查中, 有 75.73%的受访者表示自己使用 CMake 作为构建工具. 选择一个广泛流行的工具来打包库意味着你的项目更容易被别人使用. 本文将从一个简单的库的打包样例开…

考研专业课复习方法:如何高效记忆和理解?

高效记忆与理解指南 考研专业课是每个考生面临的重大挑战之一&#xff0c;它不仅要求我们掌握大量的知识点&#xff0c;还考验我们的理解和应用能力&#xff0c;为了在有限的时间内取得最佳效果&#xff0c;我们需要制定一套高效的复习策略,以下是关于如何在考研中高效记忆和理…

Linux 操作系统简介

Linux 操作系统 Linux 是一种自由和开源的操作系统&#xff0c;最初由芬兰的 Linus Torvalds 在1991年创建。它是一个类 Unix 操作系统&#xff0c;广泛用于服务器、个人电脑和嵌入式设备。Linux 操作系统的核心是 Linux 内核&#xff0c;其周围构建了各种工具和应用程序&…

【图像分类】ImageNet32 数据集下载指南

【图像分类】ImageNet32 数据集下载指南 写在最前面1. 介绍2. 访问 ImageNet 官网3. 申请下载权限**申请流程&#xff1a;** 4. 下载 ImageNet 数据集5. 注意事项6. 结论 &#x1f308;你好呀&#xff01;我是 是Yu欸 &#x1f680; 感谢你的陪伴与支持~ 欢迎添加文末好友 &am…

QT编程之HTTP服务端与客户端技术

一、HTTP 服务器实现方案 ‌QtWebApp 集成‌ 将QtWebApp源码的 httpserver 目录导入项目&#xff0c;并在 .pro 文件中添加 include ($$PWD/httpserver/httpserver.pri)‌。配置 WebApp.ini 文件定义服务参数&#xff08;IP、端口、线程池等&#xff09;&#xff0c;通过 HttpL…

关闭Windows更新

win R 进入 services.msc 找到windows更新 更新一个