【leetcode】338. Counting Bits(计算二进制数中1的位数)

原文

题目原文地址在这里

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.

Example:
For num = 5 you should return [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.

翻译理解

这道题的大意是这样的:

给出一个非负数 num,然后计算出 0<=i<=num 中每个数i的二进制表示值中的1的个数。

给了一个例子 num = 5时,计算后的返回值应该为[0, 1, 1, 2, 1, 2]

要求算法复杂度为线性时间复杂度,空间复杂度为O(n),最好不要使用任何语言的内置函数。

代码实现

class Solution(object): 
    def countBits(self, num): 
        """ 
        :type num: int 
        :rtype: List[int] 
        """ 
        num += 1 
        lst = [] 
        for i in range(num): 
            val = i 
            lst.append(0) 
            while val > 0: 
                lst[i] += val % 2 
                val = val >> 1 
         
        return lst

No comments yet.

Leave a comment

Comment form

All fields marked (*) are required

返回顶部
跳到底部