338. 比特位计数

Difficulty
easy
Tags
位运算
URL
https://leetcode-cn.com/problems/counting-bits/
Star
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
示例 1：
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10
示例 2：
输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
提示：
  • 0 <= n <= 105
进阶：
  • 很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
  • 你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）
通过次数192,373提交次数244,442

法1 暴力计算

思路
通过 n & (n-1) 将最右边的1 置为0
题解
class Solution:
    def countBits(self, n: int) -> List[int]:
        res = [0 for _ in range(n+1)]
        for i in range(0, n+1):
            res[i] = self.helper(i)

        return res
        
    def helper(self, n):
        count = 0
        while n>0:
            # n & (n-1) 将最右边的 1 置为0， 其余位不变
            n = n & (n-1)
            count += 1
        return count

法 2 位运算 递推

题解
class Solution:
    def countBits(self, n: int) -> List[int]:
        res = [0 for _ in range(n+1)]
        for i in range(1, n+1):
            # i & (i-1) 是把 i 最右边的 1 置为 0，然后 i 是 比 这个多一个1的
            res[i] = res[i & (i-1)] + 1
        return res