解决Leetcode第3470题全排列IV
3470.全排列IV
难度:困难
问题描述:
给你两个整数n和k,一个交替排列是前n个正整数的排列,且任意相邻两个元素不都为奇数或都为偶数。
返回第k个交替排列,并按字典序排序。如果有效的交替排列少于k个,则返回一个空列表。
示例1
输入:n=4,k=6
输出:[3,4,1,2]
解释:
[1,2,3,4]的交替排列按字典序排序后为:
[1,2,3,4]
[1,4,3,2]
[2,1,4,3]
[2,3,4,1]
[3,2,1,4]
[3,4,1,2]←第6个排列
[4,1,2,3]
[4,3,2,1]
由于k=6,我们返回[3,4,1,2]。
示例2
输入:n=3,k=2
输出:[3,2,1]
解释:
[1,2,3]的交替排列按字典序排序后为:
[1,2,3]
[3,2,1]←第2个排列
由于k=2,我们返回[3,2,1]。
示例3
输入:n=2,k=3
输出:[]
解释:
[1,2]的交替排列按字典序排序后为:
[1,2]
[2,1]
只有2个交替排列,但k=3超出了范围。因此,我们返回一个空列表[]。
提示:
1<=n<=100
1<=k<=1015
分析问题:
这个问题关键是要先把1至n共n个数的全排列找出来,然后根据“任意相邻两个元素不都为奇数或都为偶数”的规则生成交替排列,并按字典序排好序,剩下的输出第k个排列就好办了。生成全排列又用到了递归的方法。
程序如下:
#将一个整数插入到一个整数列表中的各个位置,形成一个新的全排列并返回
def one_into_all(a,b):n=len(b)c=[]for i in range(n+1):left=b[:i]right=b[i:]d=left+[a]+rightc.append(d)return c#生成列表a的全排列,并返回
def all_array(a):n=len(a)if n==2:return[[a[0],a[1]],[a[1],a[0]]]elif n==3:return [[a[0],a[1],a[2]],[a[0],a[2],a[1]],[a[1],a[0],a[2]],[a[1],a[2],a[0]],[a[2],a[0],a[1]],[a[2],a[1],a[0]]]else:c=[]b=a[0]for i in all_array(a[1:]):d=one_into_all(b,i)c.extend(d)c.sort()return c#检查一个列表中相邻两个整数是否都为奇数或都为偶数,如果是返回True,否则返回False
def is_odd_or_even(a):n=len(a)for i in range(n-1):if a[i]%2==0 and a[i+1]%2==0 or a[i]%2==1 and a[i+1]%2==1:return Trueelse:return False#主程序之输入部分
n=int(input('pls input n='))
k=int(input('pls input k='))
#根据输入的n值,生成元素为1至n的列表
a=list(range(1,n+1))#从1至n的全排列中去除相邻元素都为奇数或都为偶数的排列,生成交替排列
b=[]
for i in all_array(a):if is_odd_or_even(i):continueelse:b.append(i)#根据k的值,输出第k个排列或输出空列表
n=len(b)
if k<=n:print(f'生成的交替排列中的第{k}个排列为:{b[k-1]}')
else:print([])#将交替排列按一行四个排列的格式输出
k=0
print('生成的交替排列按每行4个元素排列如下:',end=' ')
for i in b:if k%4!=0:print(i,end=' ')else:print()print(i,end=' ')k=k+1
运行实例一
pls input n=4
pls input k=3
生成的交替排列中的第3个排列为:[2, 1, 4, 3]
生成的交替排列按每行4个元素排列如下:
[1, 2, 3, 4] [1, 4, 3, 2] [2, 1, 4, 3] [2, 3, 4, 1]
[3, 2, 1, 4] [3, 4, 1, 2] [4, 1, 2, 3] [4, 3, 2, 1]
运行实例二
pls input n=3
pls input k=2
生成的交替排列中的第2个排列为:[3, 2, 1]
生成的交替排列按每行4个元素排列如下:
[1, 2, 3] [3, 2, 1]
运行实例三
pls input n=2
pls input k=3
生成的交替排列中没有第3个排列,故输出[]
生成的交替排列按每行4个元素排列如下:
[1, 2] [2, 1]
全排列是解决很多问题的关键,探究生成全排列的各种方法应该是必要的。
相关文章:
解决Leetcode第3470题全排列IV
3470.全排列IV 难度:困难 问题描述: 给你两个整数n和k,一个交替排列是前n个正整数的排列,且任意相邻两个元素不都为奇数或都为偶数。 返回第k个交替排列,并按字典序排序。如果有效的交替排列少于k个,则…...
MyBatis 配置文件核心
MyBatis 配置文件核心标签解析 以下是针对你的笔记中的三个核心标签的详细解析,帮助你全面理解它们的用途和配置逻辑。 1. properties 标签:动态加载外部配置 功能 将环境相关的配置(如数据库连接、密钥等)与 MyBatis 核心配置…...
bert模型笔记
1.各预训练模型说明 BERT模型在英文数据集上提供了两种大小的模型,Base和Large。Uncased是意味着输入的词都会转变成小写,cased是意味着输入的词会保存其大写(在命名实体识别等项目上需要)。Multilingual是支持多语言的࿰…...
微信小程序接入deepseek
先上效果 话不多说,直接上代码(本人用的hbuilder Xuniapp) <template><view class"container"><!-- 聊天内容区域 --><scroll-view class"chat-list" scroll-y :scroll-top"scrollTop":…...
推荐算法和推荐系统入门第一趴
以下是推荐系统技术总结的架构梳理和建议表达思路: 从原理到生产环境:推荐系统核心技术与实战代码解析 一、推荐算法的演进图谱 传统算法三剑客 ![推荐系统算法分类示意图] (使用Mermaid绘制算法分类关系图,清晰展示技术演进&am…...
unity pico开发 四 物体交互 抓取 交互层级
文章目录 手部设置物体交互物体抓取添加抓取抓取三种类型抓取点偏移抓取事件抓取时不让物体吸附到手部 射线抓取交互层级 手部设置 为手部(LeftHandController)添加XRDirInteractor脚本 并添加一个球形碰撞盒,勾选isTrigger,调整大小为0.1 …...
基于深度学习的青花瓷图像检索系统开发与实现
目录 1.研究背景与目的 1.1课题背景 1.2研究目的 二、调研资料情况 2.1图像分割研究现状 2.2图像检索调研 2.2.1选择深度学习进行检索的原因及优势 2.2.2基于深度学习的图像检索技术的发展 2.2.3基于深度学习的图像检索的研究重点 2.3基于深度学习的图像检索方法调研 …...
uniapp 系统学习,从入门到实战(八)—— Vuex 的使用
全篇大概 4500 字(含代码),建议阅读时间 30min 📚 目录 Vuex核心概念解析在 UniApp 中集成Vuex状态管理与数据共享实践总结 一、Vuex 核心概念解析 1.1 什么是状态管理 在跨多组件的大型应用中,不同页面/组件需要共享和修改相同数据时&am…...
Vue Hooks 深度解析:从原理到实践
Vue Hooks 深度解析:从原理到实践 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家!点我试试!! 文章目录 Vue Hooks 深度解析:从原理到实践一、背景…...
django中序列化器serializer 的高级使用和需要注意的点
在 Django REST framework(DRF)中,序列化器(Serializer)是一个强大的工具,用于将复杂的数据类型(如 Django 模型实例)转换为 Python 原生数据类型,以便将其渲染为 JSON、XML 等格式,同时也能将接收到的外部数据反序列化为 Django 模型实例。以下将介绍序列化器的高级…...
靶场(二)---靶场心得小白分享
开始: 看一下本地IP 21有未授权访问的话,就从21先看起 PORT STATE SERVICE VERSION 20/tcp closed ftp-data 21/tcp open ftp vsftpd 2.0.8 or later | ftp-anon: Anonymous FTP login allowed (FTP code 230) |_Cant get dire…...
PHP Error处理指南
PHP Error处理指南 引言 在PHP开发过程中,错误处理是一个至关重要的环节。正确的错误处理不仅能够提高代码的健壮性,还能提升用户体验。本文将详细介绍PHP中常见的错误类型、错误处理机制以及最佳实践,帮助开发者更好地应对和处理PHP错误。 PHP错误类型 在PHP中,错误主…...
视频输入设备-V4L2的开发流程简述
一、摄像头的工作原理与应用 基本概念 V4L2的全称是Video For Linux Two,其实指的是V4L的升级版,是linux系统关于视频设备的内核驱动,同时V4L2也包含Linux系统下关于视频以及音频采集的接口,只需要配合对应的视频采集设备就可以实…...
【Manus资料合集】激活码内测渠道+《Manus Al:Agent应用的ChatGPT时刻》(附资源)
DeepSeek 之后,又一个AI沸腾,冲击的不仅仅是通用大模型。 ——全球首款通用AI Agent的破圈启示录 2025年3月6日凌晨,全球AI圈被一款名为Manus的产品彻底点燃。由Monica团队(隶属中国夜莺科技)推出的“全球首款通用AI…...
Mybatis集合嵌套查询,三级嵌套
三个表:房间 玩家 玩家信息 知识点:Mybatis中级联有关联(association)、集合(collection)、鉴别器(discriminator)三种。其中,association对应一对一关系、collectio…...
thinkphp5.1 在fetch模版就超时
场景 当被渲染模版不存在,请求不响应任何内容,过一会就timeout 排查过程 使用xdebug,追踪代码,发现走到D:\temporary_files\m40285_mini\40285_mini\thinkphp\library\think\exception\Handle.php,进入死循环,一直…...
Dockerfile 深入浅出:从基础到进阶全解析
Dockerfile 深入浅出:从基础到进阶全解析 各位同学,大家好!欢迎来到今天的 Dockerfile 课程。Docker 技术在当今的软件开发和部署领域可以说是非常热门,而 Dockerfile 作为构建 Docker 镜像的关键文件,掌握它对于我们…...
CAD2025电脑置要求
Windows 系统 操作系统:64 位 Microsoft Windows 11 和 Windows 10 version 1809 或更高版本。 处理器 基本要求:2.5-2.9GHz 处理器,不支持 ARM 处理器。 推荐配置:3GHz 以上处理器(基础),4GHz …...
android App主题颜色动态更换
如何在Android开发中更换主题颜色,现在他们又问了关于动态更换应用主题颜色的问题。看来他们可能在实现过程中遇到了困难,或者需要更详细的动态切换指导。首先,我需要回顾之前的回答,看看是否已经覆盖了动态切换的部分,…...
微服务,服务治理nacos,负载均衡LOadBalancer,OpenFeign
1.微服务 简单来说,微服务架构风格[1]是一种将一个单一应用程序开发为一组小型服务的方法,每个服务运行在 自己的进程中,服务间通信采用轻量级通信机制(通常用HTTP资源API)。这些服务围绕业务能力构建并 且可通过全自动部署机制独立部署。这…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
