leetcode

LeetCode 338. Counting Bits

Problem

LeetCode 338. Counting Bits

1. 题目简述

给出一个非负整数num，计算从0到num每个数字二进制表示中1的个数，并以数组形式返回。

Input: 5
Output: [0,1,1,2,1,2]

2. 算法思路

Brute Force

首先最暴力的解法肯定是每次向右移动一位，计算当前数字除以2的余数是多少，然后加和。

暴力解法（进阶版）

比如说对于32，二进制表示为“100000”，需要移动5次，计算6次，这很明显是不合理的嘛，因此就用到了一个十分巧妙的方法去掉末尾的0。

$$n = n & (n - 1)$$

以32举例，31的二进制表示是“11111”，和32做&操作后，n变为0，将从右至左第一个1给消除掉了，减少了很多不必要的运算。

Dynamic Programming

这种方法比较巧妙，我们其实可以找规律。我们假设从1找到8的二进制写法：

0 ->    0
1 ->    1
2 ->   10
3 ->   11
4 ->  100
5 ->  101
6 ->  110
7 ->  111
8 -> 1000

我们找一下规律，从4到7，不外乎就是把0、1、2、3四个数的二进制数前面加个1，多了一个1；我们可以想象，从8到15，也就是比从0到7每个数多了一个1，因此我们用一个lower变量表示比8小的每个数的1的个数，当到达下一个节点时，更新lower为1.

3. 解法

Dynamic Programming


class Solution {
    public int[] countBits(int num) {
        int pow = 1;
        int lower = 1;
        int[] res = new int[num + 1];
        Arrays.fill(res, 0);

        for (int i = 1; i <= num; i++) {
            if (i == pow) {
                pow = pow << 1;
                res[i] = 1;
                lower = 1;
            } else {
                res[i] = res[lower] + 1;
                lower++;
            }
        }

        return res;
    }
}

暴力解法进阶版:

class Solution {
    public int[] countBits(int num) {
        int[] result = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            result[i] = fastCountBits(i);
        }
        return result;
    }

    private int fastCountBits(int num) {
        int i;

        for (i = 0; num != 0; i++) {
            num = num & (num - 1);
        }

        return i;
    }
}