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

题目内容

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。
说明 :0 <= n <= 105

解题思路1

直接运用内置函数bin()和count()将从0 到 n的数转化为二进制的字符串，并且统计其中的 1 的个数，记录在列表中。

class Solution(object):
def countBits(self, n):
    list = []
    for x in range(n+1):
        str = bin(x)[2:]
        list.append(str.count('1'))
    return list

解题思路2

运用二进制编码的规律
遮住编码的最高位，可以发现剩余位数编码变化规律和之前的1~n-1位编码规律相同。设当前二进制数x最高位大小为p（1、2、4...） ，则list[x] = list[x - p] + 1。

 class Solution(object):
 def countBits(n):
    list=[0]
    p = 1
    x = 1
    while x <= n:
        q = p << 1
        while x < q :
            list.append(list[x-p] + 1)
            x +=1
            if x > n: break
        p = q
    return list

解题思路3

进一步寻找更简化的改进二进制编码的规律。如果x是奇数，则其list[x] = list[x >> 1] + 1；如果x是偶数，list[x] = list[x >> 1]。

class Solution(object):
def countBits(self, n):
    list = [0]
    for x in range(1, n+1):
       list.append(list[x >> 1] + x % 2)
    return list

Python

• append()将对象加入到列表末尾，在加入前要先定义列表list = []。