2021/03/03 每日一题 位计数

LeetCode位计数，中等难度，记录下解题思路

输入一个数num，需要求[0,num]区间内所有数对应的二进制数中1的数量

计算一个数的二进制中1的个数，可以直接将一个数转换为二进制例如5 = 2^2 + 2^0 = 101
也可以拆分为5 = 4 + 1
其中4直接是2^2对应的就是100，是除了第一位以外所有的数均为0的情况，之后加上2^0即001，那么就可以得到101
那么运用动态规划的思路：
1 = 2^0
2 = 2^1
3 = 2^1 + 2^0
4 = 2^2
5 = 2^2 + 2^0
6 = 2^2 + 2^1
7 =2^2 + 2^1 + 2^0
如果一个数是2的整次幂，那么这个数二进制对应1的个数为1
如果一个数不是2的整次幂，那么这个数可以拆分为res[i] = res[i -最近一个整数次幂的数] + 1，res数组是对应数字二进制中1的个数
例如：
res[5] = res[5-4] + 1 = 2
res[6] = res[6-4] + 1 = res[2] + 1 = 2
res[7] = res[7-4] + 1 = res[3] + 1 = res[3-2] + 1 + 1 = res[1] + 1 + 1 = 3

这样推导下来就能很清楚的看到动态规划的公式，所以最后实现的过程如下：

1. 遍历[0,num]中间所有数，并且已知res[0] = 0
2. 如果这个数是2的整数次幂就保存下来，记为high，并且这个数的count = 1
   判断整数次幂用i & (i - 1)) === 0
   例如4 = 100和3 = 011来做与运算结果就是0
   5 = 101和4 = 100做与运算结果为100不为0
3. 如果这个数不是2的整数次幂，就查用保存的high和当前数相减res[i] = res[i - high] + 1这个公式来计算结果

var countBits = function(num) {
   // 创建结果数组
    const res= new Array(num + 1).fill(0);
   // 定义当前最高位为0
    let highBit = 0;
   // 从1开始遍历整个数
    for (let i = 1; i <= num; i++) {
        // 如果是2的整数次幂
        if ((i & (i - 1)) === 0) {
            // 保存当前数
            high = i;
            // 将当前数对应的结果设为1
            res[i] = 1
            // 跳出本次循环
            continue
        }
        // 计算结果
        res[i] = res[i - high] + 1;
    }
    return res;
}