题目难度： 中等
做题日期： 2017 年 4 月 26 号
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.
没有阅读前两天总结的读者可以先看看前两篇基础介绍：
[每日一题]DP小结一：重叠子问题
[每日一题]DP二：最优子结构
DP思路
这几天一直在总结 DP 的特点，希望能找到一般性的解题思路。笔者认为，DP 题的难点在于构建最优子结构。只要构造了最优子结构，一般就比较容易解题了。
构造最优子结构的方法有两种：倒推发现 n 与 0 到 n - 1 的关系；使用 DFS 和 递归 方法，从 0 到 n 发现规律。
今天这道题的解法试图通过观察其特点发现规律。这也是一般性的思考问题的方法：
通过画图，将抽象的问题具体化
，通过具体的例子来发现规律，最后推广到 n 的规模。
假设 n = 10 ， 那么 0 到 10 对应的 二进制数 和 1 的个数 如下图所示
根据是否能被 2 整除，我们可以将 n 分成 偶数 和 奇数 。
n 为偶数
当 n 为偶数的时候， 比如 10 ， 我们可以发现其 1 的个数 与 5 的 1 的个数相等。如下图所示
实际上，通过对比 10 二进制数 1010 跟 5 的二进制数 101，我们可以发现： 5 向左移动一位后就等于 10 。所以 10 的 1 的个数 与 5 的 1 的个数相等（在左移的过程中，没有增加 1 ，只在最后面补了一个 0）。
n 为奇数
如下图所示，当 n = 9 的是，我们可以发现 9 的 1 的个数等于 4 的 1 的个数 在 加 1 。
实际上，通过对比 9 的二进制数 1001 与 4 的二进制数 100， 我们可以发现：
100(4) 左移动一位以后变成了 1000， 然后加 1 ，正好等于 1001 (9) 。所以 9 的 二进制值 的 1 个数等于 4（实际上是 9 除以 2 的值）的二进制值的 1 的个数在加 1。
