1
2
3
4
5
6
7
8
9
class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 1; i < ans.length; i++) {
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }
}

这个方法很巧妙. 一个数字往右shift一位就是自己的一半, 自己的一半有多少个1然后再看自己是不是奇数, 是奇数的话末尾是1, 我们再加个1即可.

也就是自己可以由自己一半(向下取整)往左移动一位得到, 但是移动完可能不是自己, 因为左移一位一定得到一个偶数. 我们再看我们的最后一位是否为1, 如果是再加个1, 否则就不用了.

时间复杂度: O(n)
空间复杂度: O(n) 用来装答案.