338.比特位计数

题目描述

题解

动态规划

通过二进制数的规律可知, 如果当前数字为奇数, 那么它包含1的数量一定为它前一个数的+1, 如果当前数字为偶数, 那么它包含1的数量一定与其一半数值的数相等, 例如4中1的数量与2中1的数量是相同的, 因为二倍关系只是左移或者右移的结果, 1的数量没有改变

public int[] countBits(int num) {
    int[] res = new int[num + 1];
    for (int i = 1; i <= num; i++) {
        if (i % 2 != 0) {
            res[i] = res[i - 1] + 1;
        } else {
            res[i] = res[i / 2];
        }
    }
    return res;
}