LeetCode 338. 比特位计数

题目

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

例：
输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

方法：内置函数

• ans 记录每个数的二进制表示中 1 的个数
• 循环遍历 [0, n]，计算每个数的二进制表示 num，计算每个数的二进制表示的 1 的个数，将该个数加入 ans

class Solution(object):
    def countBits(self, n):
        ans = []
        for i in range(n+1):
            num = bin(i)
            ans.append(num.count('1'))
        return ans

方法：动态规划

• ans 记录每个数的二进制表示中 1 的个数
• 循环遍历 [1, n]，计算每个数字的二进制表示的 1 的个数
  • 若数字为奇数，那么它的二进制表示的 1 的个数比前一个数大 1
    ※ 0=0 1=1 2=10 3=11
  • 若数字为偶数，那么它的二进制表示的 1 的个数和该数除以二得到的数字的二进制表示的 1 的个数相等
    ※ 2=10 4=100 8=1000

class Solution(object):
    def countBits(self, n):
        ans = [0] * (n+1)
        for i in range(1, n+1):
            if i % 2 == 1:
                ans[i] = ans[i-1] + 1
            else:
                ans[i] = ans[i/2]
        return ans

相关知识

• bin(x)： bin()
  x： 数字

• count(sub, start, end)： str.count()
  sub： 要搜索的子字符串
  start： 字符串开始搜索的位置，默认为字符串的首部
  end： 字符串结束搜索的位置，默认为字符串的尾部

参考

bin 函数：https://www.runoob.com/python/python-func-bin.html
count 函数：https://www.runoob.com/python/att-string-count.html
代码相关：https://leetcode.cn/problems/counting-bits/solution/hen-qing-xi-de-si-lu-by-duadua/