生成长度为size的达标数组,什么叫达标?达标:对于任意的 i<k<j,满足 [i] + [j] != [k] * 2。给定一个正数size,返回长度为size的达标数组。
递归缩容。
[a,b,c]→[2a-1,2b-1,2c-1,2a,2b,2c]。如果[a,b,c]符合条件,那么[2a-1,2b-1,2c-1,2a,2b,2c]也符合条件,长度扩了一倍。
[1]。长度为1。
[1,2]。长度为2。
[1,3,2,4]。长度为4。
[1,5,3,7,2,6,4,8]。长度为8。
如果size为7,从[1 5 3 7 2 6 4 8]截取左边7个元素就行。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
ret := makeNo(7)
fmt.Println(ret)
}
func makeNo(size int) []int {
if size == 1 {
return []int{1}
}
// size
// 一半长达标来
// 7 : 4
// 8 : 4
// [4个奇数] [3个偶]
halfSize := (size + 1) / 2
base := makeNo(halfSize)
// base -> 等长奇数达标来
// base -> 等长偶数达标来
ans := make([]int, size)
index := 0
for ; index < halfSize; index++ {
ans[index] = base[index]*2 - 1
}
for i := 0; index < size; i++ {
ans[index] = base[i] * 2
index++
}
return ans
}
执行结果如下: