LeetCode – 338. Counting Bits

題目來源:LeetCode – 338. Counting Bits


題目:

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到5,其中

數字0的二進制1有0個;數字1的二進制1有1個;數字2的二進制1有1個;

數字3的二進制1有2個;數字4的二進制1有1個;數字1的二進制5有2個

因此返回[0,1,1,2,1,2]

解法:

 


網站:http://wp.mlab.tw/
GitHub:https://github.com/yoll522/LeetCode
程式碼:https://github.com/yoll522/LeetCode/tree/master/338.%20Counting%20Bits

Leave a Reply

你的電子郵件位址並不會被公開。 必要欄位標記為 *