2021-06-17：生成长度为size的达标数组，什么叫达标？

原创

福大大架构师每日一题

修改于 2021-06-18 10:41:12

3270

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2021-06-17：生成长度为size的达标数组，什么叫达标？达标：对于任意的 i<k<j，满足 i + j != k * 2。给定一个正数size，返回长度为size的达标数组。

福大大答案2921-06-17：

递归缩容。

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
}

执行结果如下：