📃 题目描述

题目链接：

• 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 338. 比特位计数 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

示例 1:

输入: n = 2
输出: [0,1,1]
解释: 
0 --> 0
1 --> 1
2 --> 10

示例 2:

输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

🔔 解题思路

暴力

最简单，二进制转十进制，遍历即可

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

        for (int i = 0; i <= n; i ++) {
            String str = traverse(i);
            for (int j = 0;  j < str.length(); j ++) {
                if (str.charAt(j) == '1') {
                    res[i] ++;
                }
            }
        }
  
        return res;
    }

    // 10 进制转 2 进制
    private String traverse(int n) {
        StringBuilder sb = new StringBuilder();

        while (n != 0) {
            sb.append(n % 2);
            n /= 2;
        }

        return sb.reverse().toString();
    }
}

Brian Kernighan 算法

关键点就是：通过 x & x - 1 把 x 的最后一位 1 变成 0

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

        for (int i = 0;  i <= n; i ++) {
            // 对 i 重复执行 (i & i - 1) 操作，直到 i 所有位置都是 0
            int temp = i;
            while (temp != 0) {
                temp &= temp - 1;
                res[i] ++;
            }
        }

        return res;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：