Python算法题集_全排列

 Python算法题集_全排列

  • 题46:全排列
  • 1. 示例说明
  • 2. 题目解析
    • - 题意分解
    • - 优化思路
    • - 测量工具
  • 3. 代码展开
    • 1) 标准求解【标记数组+递归】
    • 2) 改进版一【指针+递归】
    • 3) 改进版二【高效迭代模块】
    • 4) 改进版三【高效迭代模块+极简代码】
  • 4. 最优算法
  • 5. 相关资源

本文为Python算法题集之一的代码示例

题46:全排列

1. 示例说明

  • 给定一个不含重复数字的数组 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 中的所有整数 互不相同

2. 题目解析

- 题意分解

  1. 本题是计算集合的全排列组合
  2. 基本的设计思路是递归计算组合

- 优化思路

  1. 通常优化:减少循环层次

  2. 通常优化:增加分支,减少计算集

  3. 通常优化:采用内置算法来提升计算速度

  4. 分析题目特点,分析最优解

    1. 每加一个元素,添加的组合等于旧元素全排列集合与新元素各排列一次,以此递归

    2. 可以考虑用高效迭代模块单元itertools


- 测量工具

  • 本地化测试说明:LeetCode网站测试运行时数据波动很大【可把页面视为功能测试】,因此需要本地化测试解决数据波动问题
  • CheckFuncPerf(本地化函数用时和内存占用测试模块)已上传到CSDN,地址:Python算法题集_检测函数用时和内存占用的模块
  • 本题本地化超时测试用例自己生成,详见章节【最优算法】,代码文件包含在【相关资源】中

3. 代码展开

1) 标准求解【标记数组+递归】

使用标记数组记录前置组合,递归求解

页面功能测试,马马虎虎,超过54%在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:def permute_base(self, nums):paths = []ilen = len(nums)def dfspermute(nums, path):if len(path) == ilen:paths.append(path[:])returnfor num in nums:pathleft = path[:]pathleft.append(num)numsresidue = nums[:]numsresidue.remove(num)dfspermute(numsresidue, pathleft)dfspermute(nums, [])return pathsaSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.permute_base, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))# 运行结果
函数 permute_base 的运行时间为 6231.28 ms;内存使用量为 549252.00 KB 执行结果 = 3628800

2) 改进版一【指针+递归】

使用指针标记数组记录前置位置,递归求解

页面功能测试,性能卓越,超越95%在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:def permute_ext1(self, nums):def permutation_sub(ls, start, result):if start == len(ls) - 1:result.append(list(ls))returnfor i in range(start, len(ls)):ls[i], ls[start] = ls[start], ls[i]permutation_sub(ls, start + 1, result)ls[i], ls[start] = ls[start], ls[i]perm = []permutation_sub(nums, 0, perm)return permaSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.permute_ext1, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))# 运行结果
函数 permute_ext1 的运行时间为 4993.29 ms;内存使用量为 760188.00 KB 执行结果 = 3628800

3) 改进版二【高效迭代模块】

使用高效迭代模块itertool的迭代器直接实现全排列功能

页面功能测试,性能良好,超过90%在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:def permute_ext2(self, nums):import itertoolslist_result = []for perm in itertools.permutations(nums):list_result.append(list(perm))return list_resultaSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.permute_ext2, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))# 运行结果
函数 permute_ext2 的运行时间为 2189.55 ms;内存使用量为 759268.00 KB 执行结果 = 3628800

4) 改进版三【高效迭代模块+极简代码】

使用高效迭代模块itertool的迭代器,直接一行生成结果,减少中间变量

页面功能测试,马马虎虎,超过46%在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:def permute_ext3(self, nums):import itertoolsreturn [list(perm) for perm in itertools.permutations(nums)]aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.permute_ext3, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))# 运行结果
函数 permute_ext3 的运行时间为 2016.28 ms;内存使用量为 759028.00 KB 执行结果 = 3628800

4. 最优算法

根据本地日志分析,最优算法为第4种方式【高效迭代模块+极简代码】permute_ext3

本题测试数据,似乎能推出以下结论:

  1. 减少操作的独立变量,可以提升极限性能【未必可保证可读性】
  2. itertool模块应该是用C等语言实现,效率远高于Python代码逐行实现
nums = [x for x in range(10)]
aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.permute_base, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))
result = cfp.getTimeMemoryStr(aSolution.permute_ext1, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))
result = cfp.getTimeMemoryStr(aSolution.permute_ext2, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))
result = cfp.getTimeMemoryStr(aSolution.permute_ext3, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))# 算法本地速度实测比较
函数 permute_base 的运行时间为 6231.28 ms;内存使用量为 549252.00 KB 执行结果 = 3628800
函数 permute_ext1 的运行时间为 4993.29 ms;内存使用量为 760188.00 KB 执行结果 = 3628800
函数 permute_ext2 的运行时间为 2189.55 ms;内存使用量为 759268.00 KB 执行结果 = 3628800
函数 permute_ext3 的运行时间为 2016.28 ms;内存使用量为 759028.00 KB 执行结果 = 3628800

5. 相关资源

本文代码已上传到CSDN,地址:Python算法题源代码_LeetCode(力扣)_全排列

一日练,一日功,一日不练十日空

may the odds be ever in your favor ~

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

B树和MySql索引

1.什么是B树 它是一种平衡得多叉树&#xff0c;称为B树&#xff0c;一颗M阶的B树&#xff0c;是一颗平衡的M路的多叉树&#xff0c;可以是空树或者满足一下性质&#xff1a; 根节点至少有两个孩子。每个节点都包含k-1个关键字和K个孩子&#xff0c;其中 ceil(m/2) ≤ k ≤ m …

安泰超声功率放大器技术参数有哪些

超声功率放大器是一种用于放大超声信号的设备&#xff0c;而超声功率放大器的技术参数对于设备的性能和应用场景起着重要作用。在本文中&#xff0c;我们将介绍一些常见的超声功率放大器的技术参数。 功率输出&#xff1a;超声功率放大器的功率输出是指放大器能够输出的最大功率…

【Android移动开发】Windows10平台安装Android Studio与人工智能算法模型部署案例

目录 一、Android Studio下载地址二、开发环境JDK三、开始安装Android Studio四、案例展示与搭建五、人工智能算法模型移动端部署案例参考 一、Android Studio下载地址 https://developer.android.google.cn/studio/install.html 电脑配置要求&#xff1a; 下载保存在指定文…

3.Prometheus数据模型

采样时间戳 指标 指标值平凡也就两个字: 懒和惰; 成功也就两个字: 苦和勤; 优秀也就两个字: 你和我。 跟着我从0学习JAVA、spring全家桶和linux运维等知识&#xff0c;带你从懵懂少年走向人生巅峰&#xff0c;迎娶白富美&#xff01; 关注微信公众号【 IT特靠谱 】&#xff0…

Niginx介绍和安装使用

Nginx是什么&#xff1f; Nginx (engine x) 是一个高性能的HTTP和反向代理web服务器&#xff0c;同时也提供了IMAP/POP3/SMTP服务。Nginx是由伊戈尔赛索耶夫为俄罗斯访问量第二的Rambler.ru站点&#xff08;俄文&#xff1a;Рамблер&#xff09;开发的&#xff0c;第一…

你并不了解 JavaScript:作用域与闭包 - 第二版 - 第八章:模块化模式

第八章&#xff1a;模块化模式 在本章中&#xff0c;我们将通过探索所有编程中最重要的代码组织模式之一&#xff1a;模块&#xff0c;来结束本书的正文。正如我们将看到的那样&#xff0c;模块本质上是由我们已经讲过的内容构建而成&#xff1a;这是你学习词法作用域和闭包所…

k8s(5)

目录 使用Kubeadm安装k8s集群&#xff1a; 初始化操作&#xff1a; 每台主从节点&#xff1a; 升级内核&#xff1a; 所有节点安装docker &#xff1a; 所有节点安装kubeadm&#xff0c;kubelet和kubectl&#xff1a; 修改了 kubeadm-config.yaml&#xff0c;将其传输给…

Azure Eventhub项目引入Servicebus报NoClassDefFoundError

前提 现有项目使用azure eventhub作为IOT数据载体进行数据传输。由于业务需要&#xff0c;需要同时引入servicebus。 <dependency><groupId>com.azure</groupId><artifactId>azure-messaging-servicebus</artifactId><version>7.13.3<…

springboot网站开发-使用MultipartFile上传图片文件到远程服务器

springboot网站开发-使用MultipartFile上传图片文件到远程服务器&#xff01;昨天上午在准备网站的一些 图片&#xff0c;下午在测试图片上传的模块&#xff0c;走了一些弯路&#xff0c;今天和大家分享一下&#xff0c;免得大家再走弯路。 首先&#xff0c;要和大家声明一件事…

vue3使用echarts绘制地图

vue3使用echarts绘制地图 安装echarts npm install echarts下载地图的json数据【我这里是把json数据单独粘出来然后新建了一个文件china.json】 下载中国及各个省份的地图数据引入 import chinaJson from ./china.json绘制地图 <template><div ref"myChart&q…

面试经典150题【31-40】

文章目录 面试经典150题【31-40】76.最小覆盖字串36.有效的数独54.螺旋矩阵48.旋转图像73.矩阵置零289.生命游戏383.赎金信205.同构字符串290.单词规律242.有效的字母异位词 面试经典150题【31-40】 76.最小覆盖字串 基本思路很简单&#xff0c;就是先移动右边到合适位置。再移…

网络安全与IP安全网络安全

网络安全与IP安全网络安全 网络安全 是指网络系统的硬件&#xff0c;软件以及系统中的数据收到的保护。 保护的基本属性为&#xff1a;机密性&#xff0c;身份认证&#xff0c;完整性和可用性&#xff1b; 基本特征&#xff1a;相对性&#xff0c;时效性&#xff0c;相关性…

[面试]我们常说的负载均衡是什么东西?

什么是负载均衡 如果用户量很多, 服务器的流量也随之增大, 此时出现两个问题, 软件性能下降 容易出现单点故障 为了解决这些问题, 引入了集群化架构, 也就是把一个软件同时部署在多个服务器上 集群化架构出现的问题 架构改变后又出现了两个问题 如何将请求均匀的发送到多…

大疆无人机视频删了怎么恢复?尝试这些恢复技巧

无人机拍摄的视频已经成为许多飞行爱好者和专业人士珍贵的记忆与资料。然而&#xff0c;误删视频是许多人都可能遇到的问题。当您不慎删除了大疆无人机中的视频时&#xff0c;不必过于焦虑。本文将为您详细介绍如何恢复这些误删的视频&#xff0c;帮助您找回宝贵的回忆。 图片来…

Laravel03 路由到控制器与连接数据库

Laravel03 路由到控制器与连接数据库 1. 路由到控制器2. 连接数据库 1. 路由到控制器 如下图一些简单的逻辑处理可以放在web.php中&#xff0c;也就是路由的闭包函数里面。但是大的项目&#xff0c;我们肯定不能这么写。 为什么保证业务清晰好管理&#xff0c;都应该吧业务逻辑…

【Linux深入剖析】进程优先级 | 命令行参数 | 环境变量

&#x1f4d9; 作者简介 &#xff1a;RO-BERRY &#x1f4d7; 学习方向&#xff1a;致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f4d2; 日后方向 : 偏向于CPP开发以及大数据方向&#xff0c;欢迎各位关注&#xff0c;谢谢各位的支持 目录 1.进程优先级2.Linux…

[C++]使用C++实现监控文件是否被修改

软件开发过程中经常会用到配置文件,某些应用场景要求在软件运行时动态修改配置文件,此时就需要监控配置文件是否被修改,下面我们就来看看如何使用C实现这一功能吧 软件开发过程中经常会用到配置文件&#xff0c;某些应用场景要求在软件运行时动态修改配置文件&#xff0c;此时…

国产服务器操作系统

为何记录 最近的开发工作经常接触到国产服务器操作系统的业务&#xff0c;经常被x86、arm、龙芯、鲲鹏、欧拉...搞得一脸懵逼&#xff0c;遂记之&#xff01; 操作系统 这里按照应用场景分&#xff1a; 桌面操作系统&#xff1a;主要用于pc&#xff0c;如Windows、macOS、Li…

MES系统生产订单管理:多角度全面解析

一、MES系统生产订单管理概述 MES中的生产订单管理涉及到订单的接收、处理、执行和跟踪等多个方面。MES系统生产订单管理旨在确保生产过程中的订单信息准确无误、生产进度可控&#xff0c;从而实现高效、有序的生产。 二、生产订单管理的核心功能 订单接收与处理&#xff1a;…

30-k8s集群的七层代理-ingress资源(进阶知识)

一、ingress概述 1&#xff0c;引发问题 目前使用svc资源做网络暴露&#xff0c;使用nodeport类型&#xff0c;一个业务对应一个宿主机端口&#xff0c;那么如果业务多了&#xff0c;所占用的宿主机端口也就多了&#xff0c;虽然说宿主机端口一般情况下都是够用的&#xff0c;…