比特位计数

比特位计数

题目：
给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:
输入: 2
输出: [0,1,1]

示例 2:
输入: 5
输出: [0,1,1,2,1,2]

解题思路1：分别求出每个数的 二进制中1的个数

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];

        for(int i = 0; i <= n; i++) {
            ans[i] = getAns(i);
        }

        return ans;
    }

    private int getAns(int n) {
        int count = 0;
        while(n > 0) {
            n &= (n - 1);
            count++;
        }

        return count;
    }
}

解题思路2：用动态规划解决

class Solution {
    public int[] countBits(int n) {

        int ans[] = new int[n + 1];
        ans[0] = 0;
        if(n == 0) {
            return ans;
        }
        
        ans[1] = 1;

        for(int i = 2; i <= n; i++) {
            ans[i] = ans[i & (i - 1)] + 1;
        }

        return ans;
    }
}