Manjusaka

09-01 leetcode-0338

链接 338. Counting Bits

简单题，直接写

题目：

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.

题解

这题很简单，记录2^n和非 2^n 的数的 1 的个数即可

class Solution:
    def countBits(self, num: int) -> list[int]:
        res = [0] * (num + 1)
        before = prev = 1
        for i in range(1, num + 1):
            if i == prev:
                before = res[i] = 1
                prev <<= 1
            else:
                res[i] = res[before] + 1
                before += 1
        return res