338. Counting Bits

multiplex

class Solution {
    public int[] countBits(int n) {
        //    0     0
        //    1     1
        //   10     1
        //   11     2
        //  100     1
        //  101     2
        //  110     2
        //  111     3
        // 1000     1
        // 1001     2
        // 1010     2
        // 1011     3
        // 1100     2
        // 1101     3
        // 1110     3
        // 1111     4

        int[] array = new int[n + 1];
        int nthPower = 1, i = nthPower;
        while (true) {
            int upperBound = nthPower * 2;
            while (i < array.length && i < upperBound) {
                array[i] = 1 + array[i - nthPower];
                i++;
            }

            if (i == array.length) {
                break;
            }

            nthPower = upperBound;
        }

        return array;
    }
}

odd-even

class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            if ((i & 1) == 1) {
                // 奇数
                res[i] = res[i - 1] + 1;
            } else {
                // 偶数
                res[i] = res[i >> 1];
            }
        }
        
        return res;
    }
}

Reference

338. Counting Bits
剑指 Offer II 003. 前 n 个数字二进制中 1 的个数