Counting Bits

https://leetcode.com/problems/counting-bits/description/

Given a non negative integer numbernum. For every numbersiin the range0 ≤ i ≤ numcalculate the number of 1's in their binary representation and return them as an array.

Example: Fornum = 5you should return[0,1,1,2,1,2].

Thoughts

没有做出来。

看到别人的解法，把nums分成两组：最后一位和除最后一位的前面的所有位。最后一位是否为1判断很简单，把nums%2即可。那前面所有位等于什么呢，由于是二进制，刚好等于nums/2。

Code

class Solution {
    public int[] countBits(int num) {
        int[] f = new int[num + 1];
        if (num == 0) {
            return f;
        }  
        f[0] = 0;
        f[1] = 1;
        if (num == 1) {
            return f;
        }
        for (int i = 2; i < num + 1; i++) {
            f[i] = f[i >> 1] + f[i % 2];
        }

        return f;
    }
}

Analysis

时间复杂度O(n)