338. 比特位计数 (动态规划)

力扣题解《卑鄙的异乡人，巧妙的动态规划（图解过程））》

方法一：暴力计算

思路

• 从 至 遍历，将每一个数字转换成二进制，转换同时计算包含几个
• 这里采用了模拟短除的方法，对数字不断做除法，保存余数，并将数字用商替换。

复杂度分析

• 时间复杂度 ：遍历需要 ，将每个数转二进制需要 ，其中 表示一个十进制数N，转换为二进制后的长度。

• 空间复杂度 ：最终返回的列表需要占用 空间

快乐小视频

具体代码

class Solution {
public:
    // 搞一个新的函数，来将10进制转换成2进制数。
    int trans2bit(int num){
        int ans = 0;
        // 直到num全部转换完成，才退出循环
        while(num > 0){
            // 判断当前位是0还是1
            // 无论是0还是1都添加到答案中
            ans += num % 2;
            // 不断除以2，计算下一位
            num /= 2;
        }
        // 返回二进制表示时，1的个数
        return ans;
    }
    vector<int> countBits(int num) {
        vector<int> ans(num + 1);
        // 0的结果就是0，因此从1开始循环
        for(int i = 1; i <= num; i++){
            ans[i] = trans2bit(i);
        }
        return ans;
    }
};

方法二：简单的动态规划

思路

• 这是一道很模板的线性动态规划。个人认为线性动态规划就是前人栽树后人乘凉。每个新结果的诞生，都可以依赖于前面已经确定的结果线性变化得出。

• 状态定义:

  • 表示数字 对应的二进制表示中 的数量。

• 状态转移:

  • 当 为偶数时：由二进制表示规则我们可以知道，二进制表示的最后一位为0，也就是说删去这个0，对 也不会有任何影响。因此 dp[i] = dp[i / 2]
  • 当 为奇数时：由二进制表示规则我们可以知道，二进制表示的最后一位为1，也就是说数字 因为这个1，比数字 最终结果多1。因此 dp[i] = dp[(i - 1) / 2] + 1

• 转移方程：
  

• 初始状态:

  • 所有元素置0，当计算后才进行赋值。

• 返回值:

  • 返回 列表。

复杂度分析

• 时间复杂度 ：遍历 数组需要 ，计算每个 需要 。

• 空间复杂度 ：最终返回的列表需要占用 空间

快乐小视频

具体代码

class Solution {
public:
    vector<int> countBits(int num) {
        // 预先开好空间
        vector<int> dp(num + 1);

        // 同样不需要从0开始，因为dp[0] = 0
        for(int i = 1; i <= num; i++){
            if(i % 2 == 0){ // 偶数
                dp[i] = dp[i / 2];
            }
            else{ // 奇数
                dp[i] = dp[(i - 1) / 2] + 1;
            }
        }
        
        // dp数组即为所求
        return dp;
    }
};

方法三：卑鄙的异乡人，巧妙的动态规划

思路

• 这里用到了两个位运算操作：

  1. x & 1 ：用于判断奇偶性
  2. x & (x-1)：用于删除二进制右数第一个

  原理证明1： 和 做按位与，相当于与 做按位与，当 为奇数时， 的二进制末尾为 ，此时得到的按位与结果为 ， 否则的话按位与结果为

  原理证明2： 和 做按位与。假设 形如 的形式。则 形如 ，右数第一个 被借位，变为 。按位与后，会发现做到了删除右数第一个 的效果。

• 使用位运算x & 1，我们可以替换方法一和方法二中，判断奇偶的操作。即将所有的x % 2 替换为x & 1。但需要注意的是，位运算的优先级较低，判断时需要加括号：(x & 1) == 0

• 使用位运算x & (x-1)，我们可以优化方法一中的循环条件，每次删除最右侧的1，直到数字变为0。

• 使用位运算x & (x-1)，我们还可以优化方法二中的动态规划。由于该位运算的操作效果是删除二进制右数第一个 ，则显然处理后的结果 比原结果 要小，且二者的关系满足 dp[x] = dp[y] + 1

• 状态定义:

  • 表示数字 对应的二进制表示中 的数量。

• 状态转移:

  • 当 为0时：显然dp[0]=0
  • 当 非0时：按位与之后的结果，比原数字的二进制值的1的数目少1。因此 dp[i] = dp[i & i - 1)] + 1

• 转移方程：

  • 

• 初始状态:

  • 所有元素置0，当计算后才进行赋值。

• 返回值:

  • 返回 列表。

复杂度分析

• 时间复杂度 ：遍历 数组需要 ，计算每个 需要 。

• 空间复杂度 ：最终返回的列表需要占用 空间

快乐小视频

具体代码

• 方法一优化

class Solution {
public:
    // 搞一个新的函数，计算数字num二进制表示有几个1。
    int trans2bit(int num){
        int ans = 0;
        // 直到num位0，才退出循环
        while(num > 0){
            // num不为零，说明至少还有一个1
            ans++;
            // 删去num最右侧的1
            num &= num - 1;
        }
        // 返回二进制表示时，1的个数
        return ans;
    }
    vector<int> countBits(int num) {
        vector<int> ans(num + 1);
        // 0的结果就是0，因此从1开始循环
        for(int i = 1; i <= num; i++){
            ans[i] = trans2bit(i);
        }
        return ans;
    }
};

• 方法二优化

class Solution {
public:
    vector<int> countBits(int num) {
        // 预先开好空间
        vector<int> dp(num + 1);

        // 同样不需要从0开始，因为dp[0] = 0
        for(int i = 1; i <= num; i++){
            // 转移方程：
            dp[i] = dp[i & (i - 1)] + 1;
        }
        
        // dp数组即为所求
        return dp;
    }
};