LeetCode338:比特位计数

一、题目描述

二、示例

三、条件限制

四、解题思路及代码

4.1 动态规划——最高有效位

记 $dp[i]$ 表示索引 $i$ 所对应二进制数的 $「1比特数」$。

  • 如果最高位为 $1$ 且其余位均为 $0$,即 $i \& (i-1)=0$,有 $dp[i]=1$ 。
  • $i$ 比 $i-highBit$ 的 $「1比特数」$ 多 $1$ ,即 $dp[i] = dp[i-highBit]+1$

其中,$highBit$ 是二进制最高位为 $1$ 且其余位为 $0$ 的数,$i$ 和 $highBit$ 的二进制位数相等。

1
2
3
4
5
6
7
8
9
class Solution:
def countBits(self, n: int) -> List[int]:
dp, h = [0 for _ in range(n+1)], 2
for i in range(1, n+1):
if i & (i-1) == 0:
h = i
dp[i] = 1
dp[i] = dp[i - h] + 1
return dp

4.2 动态规划——最低有效位

对于正整数 $x$ ,将其二进制表示右移一位,得到的数是 $\lfloor \frac{x}{2} \rfloor$,如果 $dp[\lfloor \frac{x}{2} \rfloor]$ 的值已知,则可以得到 $dp[x]$ 的值:

  • 如果 $x$ 是偶数, 则 $dp[x]=dp[\lfloor \frac{x}{2} \rfloor]$;
  • 如果 $x$ 是奇数,则 $dp[x]=dp[\lfloor \frac{x}{2} \rfloor]+1$;
1
2
3
4
5
6
class Solution:
def countBits(self, n: int) -> List[int]:
dp = [0] * (n+1)
for i in range(1, n + 1):
dp[i] = (dp[i >> 1] + (i & 1))
return dp

五、补充

  • 判断一个二进制数是否最高位为 $1$ 且其余位为0:$x\&(x-1)==0$ ;

  • $x=x\&(x-1)$,该运算将 $x$ 的二进制数最后一个 $1$ 变为 $0$。