Day 30 - 338.counting bits

Day30 - 338.比特位计数

LeetCode 338.比特位计数

题目链接：

https://leetcode.cn/problems/counting-bits/

1. 题目描述

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

举个例子：

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

2. 知识回顾

动态规划是一种通过将原问题分解为子问题来求解复杂问题的算法思想。它通常用于求解最优化问题，例如最长公共子序列、背包问题等。动态规划的核心思想是将原问题分解为若干个子问题，通过求解子问题的最优解自下而上推导出原问题的最优解。

3. 思路解析

如果对区间[0, n]上的数逐个求对应二进制中1的个数是比较耗时的，下面来介绍使用动态规划来解此题。动态规划的关键是推导状态转移公式和边界条件处理。

下面介绍这道题目两种不同状态转移公式。

4. 方法零

暴力做法。其实就是 LeetCode.191 加了个外循环，思路非常简单。

对区间[0, n]上的数逐个求对应二进制中1的个数

4.1. C++代码

时间复杂度 后面两种方法可以降到

class Solution
{
public:
    vector<int> countBits(int n)
    {
        int res_len = n + 1;
        vector<int> res(res_len, 0);
        // 对于 0~n 逐位求解运算
        for (int i = 0; i < res_len; i++)
        {
            n = i;
            while (n)
            {
                // 减少存储二进制，计算一位就判断一位
                if (n & 1)
                {
                    res[i]++;
                }
                n = n >> 1;
            }
        }
        return res;
    }
};

5. 方法一

首先复习一下二进制的基本操作，如何获取n对应二进制的最右边一位和怎样将n对应的二进制向右移一位。

获取n对应二进制最右面一位有两种方式：

1. n和1进行与运算n & 1可以获取n对应二进制的最右面一位。

2. n对2取余n % 2即可获取n对应二进制的最右面一位。

将n对应的二进制右移一位有两种方式：

1. 直接使用编程语言自带的右移符号，比如c++可以写为n >> 1。

2. n / 2 也可以将n对应的二进制右移一位。

进入正题，定义dp[i]为i的二进制中1的个数, 观察整数区间[0,4]对应的二进制。

把4对应的二进制向右移动一位，就变成了2对应的二进制，4和2的二进制中的1是相同的。

把3对应的二进制向右移动一位，就变成了1对应的二进制，3的二进制比1的二进制中1的个数多1。

总结上面的规律，得到状态转移公式如下：

如果整数i为偶数，也就是i的二进制最右面的bit位为0，这个时候右移，二进制中的1并没有损失，dp[i] = dp[i/2]。

如果整数i为奇数，也就是i的二进制最右面的bit位为1，这个时候右移，二进制中的1会减少一个，dp[i] = dp[i/2] + 1。

边界条件为： dp[0] = 0。

5.1. C++代码

class Solution
{
public:
    vector<int> countBits(int n)
    {
        int res_len = n + 1;
        vector<int> res(res_len, 0);
        for(int i = 1; i < res_len; i++)
        {
            // 如果是偶数
            // 递归公式：res[i] = res[i/2]
            if((i&1) == 0)
            {
                res[i] = res[i >> 1];
            }
            // 如果是奇数
            // 递归公式：res[i] = res[i/2] + 1
            else if((i&1) != 0)
            {
                res[i] = res[i >> 1] + 1;
            }
        }
        return res;
    }
};

6. 方法二

我们先介绍一个骚操作，对于一个整数n，n & (n - 1)可以将n的二进制最右边值为1的bit位置为0。

在纸上继续按照上面步骤模拟一遍，会帮助大家更好的理解。

根据上面的操作可以知道n的二进制比n&(n-1)的二进制中的1多了1个，这样就可以得到状态转移公式：

边界条件为： dp[0] = 0。

6.1. C++代码

骚公式，我也不懂怎么推出来的...

但可以背下来的结论：

• n & (n - 1)可以将n的二进制最右边值为1的bit位置为0。

class Solution
{
public:
    vector<int> countBits(int n)
    {
        int res_len = n + 1;
        vector<int> res(res_len, 0);
        for (int i = 1; i < res_len; i++)
        {
            // 递归公式
            // 不用管奇数还是偶数
            res[i] = res[i&(i-1)] + 1;
        }
        return res;
    }
};

7. 复杂度分析

时间复杂度： 后面两种方法都是O(n)，因为只遍历一遍区间[0, n]。

空间复杂度： 后面两种方法都是O(n)，只用到一个长度为n+1的数组dp。

8. Redo. 02/08

暴力，复杂度O(nlogn)

vector的构造方法：

• vector<int> vec(vec.size(), init_val)

class Solution
{
public:
    vector<int> countBits(int n)
    {
        vector<int> res(n+1, 0);
        for(int i = 0; i <= n; i++)
        {
            int num = i;
            while(num)
            {
                if(num & 1 == 1)
                {
                    res[i]++;
                }
                num = num >> 1;
            }
        }
        return res;
    }
};

动态规划、位运算

class Solution
{
public:
    vector<int> countBits(int n)
    {
        vector<int> res(n+1, 0);
        for(int i = 1; i <= n; i++)
        {
            if(i % 2 == 0)
            {
                res[i] = res[i / 2];
            }
            else
            {
                res[i] = res[i / 2] + 1;
            }
        }
        return res;
    }
};