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 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.
解題想法：
這題的題目是輸入一個 10 進制的數，然後印出一段 list ，這段 list 是從 0 到 這個數字的每個位數會有多少個 1，下圖有範例。
--------------------------
10 進制 | 2 進制 | 幾個 1
--------------------------
0 000 0
1 001 1
2 010 1
3 011 2
4 100 1
5 101 2
6 110 2
7 111 3
8 1000 1在這當中我們有發現兩種規律，第一個就是到 8 時，前面的數又全部重來了，所以我們可以按照這個邏輯去寫演算法，第二個是更簡單的方法，當 2 以後，只要他的本身除以 2 就等於了那個數列的 1 的數再加上 餘數 就可以推算出他有幾個 1，例如
- 初始值 num = [0, 1]
- 2 = num[int (2 / 2)] + num[(2 %2)] = 2
num = [0, 1, 1]
- 3 = num[int (3 / 2)] + num[(3 %2)] = 2
num = [0, 1, 1, 2]
- 4 = num[int (4 / 2)] + num[(4 %2)] = 1
num = [0, 1, 1, 2, 1]
- 5 = num[int (5 / 2)] + num[(5 %2)] = 2
num = [0, 1, 1, 2, 1, 2]
- 6 = num[int (6 / 2)] + num[(6 %2)] = 2
num = [0, 1, 1, 2, 1, 2, 2]
- 7 = num[int (7 / 2)] + num[(7 %2)] = 3
num = [0, 1, 1, 2, 1, 2, 2, 3]
非常的好懂對吧，另外要注意的是如果 小於 1 時，初始值記得要設 [0]，即可。
- Runtime: 76 ms, faster than 59.79%
- Memory Usage: 16.8 MB, less than 32.64%
感想
發現有時候，在寫 leetcode 時，再會去思考這題有沒有 pattern 可以依循，覺得有點小可惜，或許這就是刷 leetcode 的原因，透過更多的題目學著讓自己在面對職場業務時，能有相同的思維去思考，而不是一股腦地下去做。
