【LeetCode】338.Counting Bits

1 问题

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.

1.1 Example 1

Input: n = 2
Output: [0,1,1]
Explanation:

0 –> 0
1 –> 1
2 –> 10

1.2 Example 2

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:

0 –> 0
1 –> 1
2 –> 10
3 –> 11
4 –> 100
5 –> 101

Constraints

• 0 <= n <= $10^5$

2 解题思路

统计每个数字的二进制含1的个数，可参考【LeetCode】191.Number of 1 Bits的解法二，经典求解。

3 代码

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

    private int hammingWeight(int n) {
        int ans = 0;
        while (n != 0) {
            n = n & (n - 1);
            ans++;
        }
        return ans;
    }
}