338. Counting Bits

multiplex

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
    }
}

References

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