编写一个算法来返回一个数组,使得1..n中的每个数字k恰好发生两次,与其副本相距k距离

Question

在一次采访中询问了这个问题.

对于给定的整数n> = 3,返回大小为2n的数组,使得从1到n的每个数字k恰好发生两次,并且每个数字和它的重复以等于该数字的距离分开.

功能签名:

int* buildArray(int n)

例如,对于n = 3:

3, 1, 2, 1, 3, 2

编号2:第一个位置3和第二个位置6,所以距离6 - 3 - 1 = 2.
编号3:第一个3位置1,第二个3位置5,距离5 - 1 - 1 = 3.

对于n = 4:

4, 1, 3, 1, 2, 4, 3, 2

Answer 1

这是一个精确的覆盖问题,您可以使用算法X解决.(它是一个比数独更好,更简单的例子.)你有以下约束:

• 每个号码必须使用exaclty两次
• 阵列中的每个插槽只能被一个数字占用

对于n = 3的问题,您将得到以下矩阵:

     [0] [1] [2] [3] [4] [5]  1   2   3
     --- --- --- --- --- --- --- --- ---
#0    X       X               X
#1        X       X           X
#2            X       X       X
#3                X       X   X

#4    X           X               X
#5        X           X           X
#6            X           X       X

#7    X               X               X
#8        X               X           X          

列[x]意味着使用了插槽x; plain x表示x已放置数字.#0到#3行描述了可能的位置,#4到#6两个位置,#7和#8两个可能放置三个.这将产生两个(镜像)解决方案:

2 3 1 2 1 3     (#2 + #4 + #8)
3 1 2 1 3 2     (#1 + #6 + #7)

例如,并非所有n个产量解决方案都没有针对5和6的解决方案.