leetcode/338CountingBits

338 Counting Bits

不想解释

my solution (没脸说…)

这样的东西必定有规律, 找出来就好了

func countBits(num int) []int {
    ret := []int{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4}
    last := []int{1, 2, 2, 3, 2, 3, 3, 4}

    for i, size := 3, 16; size <= num; i++ {
        beg := size - size / 4

        for beg + 4 <= size {
            last = append(last[:], ret[beg:]...)
            beg = beg + (size - beg) / 2
        }

        last = append(last[:], []int{i, i + 1, i + 1, i + 2}...)
        ret = append(ret[:], last[:]...)
        size *= 2
    }

    ret = ret[:num + 1]
    return ret
}

规律如下, 每次的增加都是上次的一半的递归 (我不知道怎么解释这种规律, 感觉语言很苍白…)

0,1,1,2,
1,2,2,3,
1,2,2,3, 2,3,3,4,
1,2,2,3, 2,3,3,4, 2,3,3,4, 3,4,4,5,
1,2,2,3, 2,3,3,4, 2,3,3,4, 3,4,4,5, 2,3,3,4, 3,4,4,5, 3,4,4,5, 2,3,3,4, 3,4,4,5, 4,5,5,6

仔细观察一下就发现了

我本来以为我的解法很不错, 计算次数很少, 几乎没有, 大部分的运算都是 append, 应该会很快, 然而…

那个几十毫秒的不是我的, 800/900 的才是 = =

best solution

func countBits(num int) []int {
    result := make([]int, num+1)
    for i := 1; i <= num; i++ {
        result[i] = result[i & (i-1)] + 1
    }
    return result
}

他是通过计算出来的, 比我好在于, 他不会计算多余的, 然后需要裁剪

(BTW 这个算法与我原算法的速度相差无几, 但是等价的 C++ 代码却只需要几十毫秒)

(加上 tie 和 sync_with_stdio, 可能速度能更快, 我不禁陷入了沉思…)