看了题目，觉得第二题是用DP，最近DP接触的比较多，就直接跳过第一题。然而我开始暴力穷举，然而调试时还是最后差一步出错，难受的鸭皮。0分机试，哈哈哈。
第一题
题目：有n个物品，编号为1-n现将其重新排列，但要求相邻的两物品编号差值绝对值不等于1,按字典序输出所有满足要求的方案。
输入：给定-个整数n，1<=n <=10
比如：输入4，输出
# 2，4，1，3
# 3，1，4，2
采用递归的思想，seq(l)表示给定list求出满足条件的序列当l只包含两个元素比如l=[1,3]时，只需判断它们的差值是否为1，如果不是1就返回l的正序和反序list，比如[[1,3],[3,1]]
当l长度大于2的时候，可以这样来处理。比如l=[1,3,4]
遍历l中每个个元素，将该元素放在第一位，判断结果是否合理，比如4
首先可以求得 剩下的元素[1,3] 的可行序列tmp=[[1,3],[3,1]]
然后判断tmp的每个序列，如果它的第一个元素跟拿出的第一个元素差值不是1的话，将其拼接在一起结果就是可行序列，比如4跟tmp[0][0]差值为3，得到可行序列[4,1,3],而跟tmp[1][0]差值为1,序列不可行
def seq(l): a=[] if len(l)==2 and abs(l[0]-l[1])!=1: a.append(l) a.append([l[1],l[0]]) return a for i in range(len(l)): tmp=seq(l[0:i]+l[i+1:]) for tp in tmp: if abs(tp[0]-l[i])!=1: a.append([l[i]]+tp) return a n=4 ln=list(range(1,n+1)) re=seq(ln) print(re)
第二题：
题目大概是给定一个序列a，a的长度是n，和一个整数m，要求判断序列a中有多少子序列中最多的数字数量大于m
比如
a=[1 2 1 2 5]
m=2
a的区间[1,3][1,4][1,5][2,4][2,5]<下标从1开始>，五个区间中最多的数字大于2。
因此输出5.
DP：
定义F[ i ][ j ]=0，1表示从i到j的序列中的中最多数字的数量是否大于2
首先初始化每个长度为1的子序列
当i <= j时，当F[ i ][ j-1 ]为1 或者 从i到j-1的序列中与第j个元素相同的数量大于等于m-1 时 F[ i ][ j ]=1，否则为0
当i > j时，当F[ i ][ j+1 ]为1 或者 从i到j+1的序列中与第j个元素相同的数量大于等于m-1 时 F[ i ][ j ]=1，否则为0
当i > j时，当F[ i ][ j+1 ]为1 或者 从i到j+1的序列中与第j个元素相同的数量大于等于m-1 时 F[ i ][ j ]=1，否则为0
a=[1,2,1,2,3,2] m=2 F=[[0]*len(a) for _ in range(len(a))] ##初始化每个长度为1的子序列，忘记题目有没有设m>=2了 for i in range(len(a)): if m<2: F[i][i]=1 ## for i in range(len(a)): for j in range(i+1,len(a)): if F[i][j-1]==1 or str(a[i:j]).count(str(a[j]))>=m-1: F[i][j]=1 for j in range(i-1,-1,-1): if F[i][j+1]==1 or str(a[j+1:i]).count(str(a[j]))>=m-1: F[i][j]=1 ##F[i][j]=F[j][i] print(sum([sum(F[i][i:]) for i in range(len(F))]))
奈何最后还是差一步美满，机试结束5分钟后调试成功。
感觉我这方法时间复杂度跟暴力没什么区别。
全部评论
(5) 回帖