338. 比特位计数

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 616 阅读时长 ≈ 2 分钟

考点

  • 比特位变化规律，按最高位变化、最低位变化与Brian Kernighan算法三种角度分析

题解

同下

思路

假设i代表当前十进制数字，dp[i]代表十进制数字i的1个数

最高有效位

设i的最高有效位保存至变量highBit；显然110是由100 + 010组成，101是由100 + 001组成，满足：

i的1个数 = 1[代表highBit] + (i - highBit)的1个数

将其转化为动态规划转移方程： \[ dp\left[ i \right] =1+dp\left[ i-highBit \right] \] 遇到001、010这类2的幂次，代表有新的进位；此时更新highBit变量，避免后续数字重复计算highBit

如果范围不大，也可以先将范围内所有的highBit通过打表存入数组，在许多场景都有该应用

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
	public:
		vector<int> countBits(int n) {
			vector<int> dp(n + 1, 0);
			int highBit = 0;
			for (int i = 1; i <= n; i++) {
				if (!(i & (i - 1))) highBit = i;
				dp[i] = dp[i - highBit] + 1;
			}
			return dp;
		}
};

时间复杂度：\(O\left( n \right)\)

空间复杂度：\(O\left( n \right)\)，新增了dp数组存储结果

最低有效位

根据奇偶性分析

  • 若i是偶数，1个数肯定与i/2一致，因为i是由i/2的比特位向左移一位而成

    比如100是010向左移了一位，1个数保持不变

  • 若i是奇数，必满足i的1个数 = i/2的1个数 + 1

    比如111是011向左移一位后再加上001

将其转化为动态规划转移方程： \[ dp\left[ i \right] =\begin{cases} dp\left[ i/2 \right] \text{，}i\text{为偶数}\\ dp\left[ i/2 \right] +1\text{，}i\text{为奇数}\\ \end{cases} \]

1
2
3
4
5
6
7
8
9
10
class Solution {
	public:
		vector<int> countBits(int n) {
			vector<int> dp(n + 1, 0);
			for (int i = 1; i <= n; i++) {
				dp[i] = i & 1 ? dp[i / 2] + 1 : dp[i / 2];
			}
			return dp;
		}
};

时间复杂度：\(O\left( n \right)\)

空间复杂度：\(O\left( n \right)\)，新增了dp数组存储结果

Brian Kernighan算法

根据i & (i - 1)可以去掉i的最低有效1这一性质，满足：

i的1个数 = 1[代表Brian Kernighan操作去掉的1] + (i & (i - 1))的1个数

将其转化为动态规划转移方程： \[ dp\left[ i \right] =1+dp\left[ i\,\,\& \left( i-1 \right) \right] \]

1
2
3
4
5
6
7
8
9
10
class Solution {
	public:
		vector<int> countBits(int n) {
			vector<int> dp(n + 1, 0);
			for (int i = 1; i <= n; i++) {
				dp[i] = dp[i & (i - 1)] + 1;
			}
			return dp;
		}
};

时间复杂度：\(O\left( n \right)\)

空间复杂度：\(O\left( n \right)\)，新增了dp数组存储结果