🟢 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

LeetCode 提示

题目难度 简单

原题链接 🔗 leetcode

解析 index.md

偷师官方教程，可以利用这么算法：Brian Kernighan 算法

对于任意整数 x，令 x = x & (x−1)，该运算将 x 的二进制表示的最后一个 1 变成 0。

所以只要反复执行直到x=0，执行次数即为 1 的个数。

题解 1.py

class Solution:    def countBits(self, n: int) -> List[int]:        def countOnes(nn: int) -> int:            cnt = 0            while nn:                cnt += 1                nn = nn & (nn-1)            return cnt                res = [0]        for i in range(1, n+1):            res.append(countOnes(i))                return res

解析 2.md

根据公式可得：

y = x & (x-1)bits[y] = bits[x] - 1bits[x & (x-1)] = bits[x] - 1

题解 2.动态规划.py

class Solution:    def countBits(self, n: int) -> List[int]:        bits = [0]
        for i in range(1, n+1):            bits.append(bits[i &(i-1)] + 1)                return bits