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, num]范圍內的數分別計算它們的二進制數中1的個數，用數組形式返回。
For num = 5 you should return [0,1,1,2,1,2].
動態規劃解。其實這是道找規律的題目，我們首先列出0-15的數對應的二進制中1的個數
| 數字 | 二進制中1的個數 | 遞推關系式 |
|---|---|---|
| 0 | 0 | dp[0] = 0 |
| 1 | 1 | dp[1] = dp[1-1] + 1 |
| 2 | 1 | dp[2] = dp[2-2] + 1 |
| 3 | 2 | dp[3] = dp[3-2] + 1 |
| 4 | 1 | dp[4] = dp[4-4] + 1 |
| 5 | 2 | dp[5] = dp[5-4] + 1 |
| 6 | 2 | dp[6] = dp[6-4] + 1 |
| 7 | 3 | dp[7] = dp[7-4] + 1 |
| 8 | 1 | dp[8] = dp[8-8] + 1 |
| 9 | 2 | dp[9] = dp[9-8] + 1 |
| 10 | 2 | dp[10] = dp[10-8] + 1 |
| 11 | 3 | dp[11] = dp[11-8] + 1 |
| 12 | 2 | dp[12] = dp[12-8] + 1 |
| 13 | 3 | dp[13] = dp[13-8] + 1 |
| 14 | 3 | dp[14] = dp[14-8] + 1 |
| 15 | 4 | dp[15] = dp[15-8] + 1 |
綜上，遞推關系式為 dp[n] = dp[n - offset] + 1 (這個規律還真不怎么好找)，而offset的更新規律為，每當 offset * 2等于n時，offset就需要更新，即乘以2.
class Solution(object): def countBits(self, num): """ :type num: int :rtype: List[int] """ # 0-num有num + 1個數 dp = [0] * (num + 1) offset = 1 for n in range(1, num + 1): # 根據規律，只要index = 2 * offset，offset需要乘以2 if offset * 2 == n: offset *= 2 # dp[index] = dp[index - offset] + 1 dp[n] = dp[n - offset] + 1 return dp新聞熱點
疑難解答
