Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.
给定非负整数num。 对于0≤i≤_n范围内的每个数字i，计算其二进制表示中的1的数量并将它们作为数组返回。
Example 1:
Input: 2
Output: [0,1,1]
Example 2:
Input: 5
Output: [0,1,1,2,1,2]
Follow up:
- It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
- Space complexity should be O(n).
-
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
- 很容易想出一个运行时间为O（n * sizeof（整数））的解决方案。 但你可以在线性时间O（n）/可能在一次通过吗？
- 空间复杂度应为O（n）。
- 你能像老板那样做吗？ 不使用c ++或任何其他语言的__builtin_popcount之类的内置函数。
python实践：
- 将十进制转化为二进制之后，再转化为列表，统计其中1的数量
class Solution:
def countBits(self, num: int) -> List[int]:
l = []
for c in range(num+1):
c = list(bin(c))
t = 0
for i in c:
if i == '1':
t += 1
l.append(t)
return l
- 通过观察规律
[2-3]中1的个数是[0-1]中个数对应加一；[4-7]是[0-3]对应加一；[8-15]是[0-7]对应加一；…… 本质上，是将最高位的1变成0得到对应的较小的数。
def countBits2(self, num):
dp = [0]
i = 0
while True:
for j in range(1<<i, 1<<(i+1)):
print(j)
if j > num:
return dp
dp.append(1+dp[j-(1<<i)])
i += 1
return dp
