LeetCode 338 Counting Bits

比特位计数

题意

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

示例 1:

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

示例 2:

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

解法

此题是 LeetCode 191 Number of 1 Bits 的拓展版, 可以利用那道题的两种算法, 只不过套个循环, 时间和空间复杂度都是 O(n).

那两种解法就不说了. 这里说下另一种解法.

这里分为 2 的倍数 和 非 2 的倍数 两种数.

他们有一个区别就是二进制的最低位是否为 1.

2 的倍数其二进制最低位都是 0. 非 2 的倍数其二进制最低位都是 1.

除 2 或右移一位后, 等于是去掉最低位, 那么既然 2 的倍数最后一位都是 0, 所以对于 2 的倍数 除 2 或右移一位后, 数字 1 的个数并不会变.

那么对于非 2 的倍数 n, n 肯定比 n - 1 的二进制中 1 的个数多一位. 如 n = 1111, n - 1 = 1110.

class Solution {
    public int[] countBits(int num) {
        int[] arr = new int[num + 1];
        for (int i = 0; i <= num; i++) {
            if (i % 2 == 0) {
                arr[i] = arr[i >> 1];
            } else {
                arr[i] = arr[i - 1] + 1;
            }
        }
        return arr;
    }
}

时间复杂度 O(n), 空间复杂度 O(n).