2021-06-17：生成长度为size的达标数组，什么叫达标？达标：对于任意的 i＜k＜j，满足 [i] + [j] != [

福大大架构师每日一题

发布于 2021-08-05 16:10:49

3360

发布于 2021-08-05 16:10:49

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

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
}

执行结果如下：