比特位计数

一题超多解

Leetcode Link: 338. 比特位计数 - 力扣（LeetCode）

题目

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

解法一

思路： 有规律的

任意一个数字 $num$ ，$(num>0)$ 可以写成这种形式：$num=2^m+x$ 其中，$2^m\le num<2^{m+1}$

这样，$num$ 中所含有的数字 1 的个数就是 1 加上数字 $x$ 所含有的 1 的个数

当数字遍历到 $num$ 的时候，一定已经走过了$x$，因此这里可以直拿来用

题解：

class Solution:
    def countBits(self, n: int) -> List[int]:
        if n == 0:
            return [0]
 
        res = [0]
        for val in range(1, n+1):
            m = log2(val)
            i = val - 2**floor(m)
 
            n1 = 1 + res[i] if i!=0 else 1
            res.append(n1)
        return res

解法二

思路：暴力法，遍历每个数字，并统计每个数字中 1 的个数

题解：

class Solution:
    def countBits(self, n: int) -> List[int]:
        res = []
        for i in range(n + 1):
            res.append(bin(i).count("1"))
        return res

Note

• bin(num) : 将十进制数字 num 转变成二进制表示的数字的字符串形式
• str.count(c): 统计字符串中str中字符c的个数

解法三

思路：暴力递归 对于数字 $num$, 有如下的情况成立

1. 如果 $num$ 是偶数，那么它的二进制 1 的位数与 $num/2$ 的二进制 1 的位数相等
   • 因为偶数的二进制末尾是 0，右移一位等于 $num/2$，而二进制中 1 的个数没有变化。
2. 如果 $num$ 是奇数，那么它的二进制 1 的位数与 $num-1$ 的二进制 1 的位数多 1 个，此时$num-1$是偶数，回到情况1。即所以奇数 $num$ 的二进制 1 的个数等于 $num/2$ 中二进制 1 的位数 +1.

题解：

class Solution(object):
    def countBits(self, num):
        res = []
        for i in range(num + 1):
            res.append(self.count(i))
        return res
    
    def count(self, num):
        if num == 0:
            return 0
        if num % 2 == 1:
            return self.count(num - 1) + 1
        return self.count(num // 2)

解法四

思路：记忆化搜索

对解法三进行改进

题解：

class Solution(object):
    def countBits(self, num):
        self.memo = [0] * (num + 1)
        res = []
        for i in range(num + 1):
            res.append(self.count(i))
        return res
    
    def count(self, num):
        if num == 0:
            return 0
        if self.memo[num] != 0:
            return self.memo[num]
        if num % 2 == 1:
            res = self.count(num - 1) + 1
        else:
            res = self.count(num // 2)
        self.memo[num] = res
        return res

解法五

思路 改写为动态规划

题解

class Solution:
    def countBits(self, num):
        res = [0] * (num + 1)
        for i in range(1, num + 1):
            res[i] = res[i >> 1] + (i & 1)
        return res

启发和联系

[参考1]((https://leetcode.cn/problems/counting-bits/solution/yi-bu-bu-fen-xi-tui-dao-chu-dong-tai-gui-3yog/): 解法三四五