LeetCode338:比特位计数

发表于 更新于 分类于 阅读次数： 本文字数： 884 阅读时长 ≈ 1 分钟

一、题目描述

二、示例

三、条件限制

四、解题思路及代码

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\)。