企业网站功能怎么设计,网页平台,北京企业网站设计报价,wordpress 不同分类不同模板3470.全排列IV
难度#xff1a;困难
问题描述#xff1a;
给你两个整数n和k#xff0c;一个交替排列是前n个正整数的排列#xff0c;且任意相邻两个元素不都为奇数或都为偶数。
返回第k个交替排列#xff0c;并按字典序排序。如果有效的交替排列少于k个#xff0c;则…3470.全排列IV
难度困难
问题描述
给你两个整数n和k一个交替排列是前n个正整数的排列且任意相邻两个元素不都为奇数或都为偶数。
返回第k个交替排列并按字典序排序。如果有效的交替排列少于k个则返回一个空列表。
示例1
输入n4,k6
输出[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]
由于k6我们返回[3,4,1,2]。
示例2
输入n3,k2
输出[3,2,1]
解释
[1,2,3]的交替排列按字典序排序后为
[1,2,3]
[3,2,1]←第2个排列
由于k2我们返回[3,2,1]。
示例3
输入n2,k3
输出[]
解释
[1,2]的交替排列按字典序排序后为
[1,2]
[2,1]
只有2个交替排列但k3超出了范围。因此我们返回一个空列表[]。
提示
1n100
1k1015
分析问题
这个问题关键是要先把1至n共n个数的全排列找出来然后根据“任意相邻两个元素不都为奇数或都为偶数”的规则生成交替排列并按字典序排好序剩下的输出第k个排列就好办了。生成全排列又用到了递归的方法。 程序如下
#将一个整数插入到一个整数列表中的各个位置形成一个新的全排列并返回
def one_into_all(a,b):nlen(b)c[]for i in range(n1):leftb[:i]rightb[i:]dleft[a]rightc.append(d)return c#生成列表a的全排列并返回
def all_array(a):nlen(a)if n2:return[[a[0],a[1]],[a[1],a[0]]]elif n3: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[]ba[0]for i in all_array(a[1:]):done_into_all(b,i)c.extend(d)c.sort()return c#检查一个列表中相邻两个整数是否都为奇数或都为偶数如果是返回True否则返回False
def is_odd_or_even(a):nlen(a)for i in range(n-1):if a[i]%20 and a[i1]%20 or a[i]%21 and a[i1]%21:return Trueelse:return False#主程序之输入部分
nint(input(pls input n))
kint(input(pls input k))
#根据输入的n值生成元素为1至n的列表
alist(range(1,n1))#从1至n的全排列中去除相邻元素都为奇数或都为偶数的排列生成交替排列
b[]
for i in all_array(a):if is_odd_or_even(i):continueelse:b.append(i)#根据k的值输出第k个排列或输出空列表
nlen(b)
if kn:print(f生成的交替排列中的第{k}个排列为{b[k-1]})
else:print([])#将交替排列按一行四个排列的格式输出
k0
print(生成的交替排列按每行4个元素排列如下,end )
for i in b:if k%4!0:print(i,end )else:print()print(i,end )kk1
运行实例一
pls input n4
pls input k3
生成的交替排列中的第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 n3
pls input k2
生成的交替排列中的第2个排列为[3, 2, 1]
生成的交替排列按每行4个元素排列如下
[1, 2, 3] [3, 2, 1] 运行实例三
pls input n2
pls input k3
生成的交替排列中没有第3个排列故输出[]
生成的交替排列按每行4个元素排列如下
[1, 2] [2, 1] 全排列是解决很多问题的关键探究生成全排列的各种方法应该是必要的。
