image.png

解法

简单解法，时间复杂度为O(nlogn)

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int count = countOnes(i);
            ans[i] = count;
        }
        return ans;
    }

    public int countOnes(int x) {
        int ones = 0;
        // x二进制最后一个1变成0
        while (x > 0) {
            x &= (x - 1);
            ones++;
        }
        return ones;
    }
}

优化解法,时间复杂度为O(n)

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        int highBits = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highBits = i;  
            }
            // 动态规划，highBits为2的次幂，减去以后的值加1
            ans[i] = ans[i - highBits] + 1;
        }
        return ans;
    }
}