My code:
public class Solution {
public int[] countBits(int num) {
if (num < 0) {
return null;
}
int[] ret = new int[num + 1];
ret[0] = 0;
int pow = 1;
for (int i = 1, t = 0; i <= num; i++, t++) {
if (i == pow) {
pow = 2 * pow;
t = 0;
}
ret[i] = ret[t] + 1;
}
return ret;
}
}
这道题目并没有做出来。
看了hint，试着找规律，画了这么一幅图。
FullSizeRender.jpg
但愚蠢的是，我只找到了表面上的规律，尝试着写出来，发现很烦。
于是看答案。
reference:
https://discuss.leetcode.com/topic/41785/simple-java-o-n-solution-using-two-pointers
发现
[0] -> +1 [1]
[0, 1] -> +1 [2, 3]
[0, 3] -> +1 [4, 7]
[0, 7] -> +1 [8, 15]
[0, 15] -> +1 [16, 31]
[0, 31] -> +1 [32, 63]
...
然后就可以写一个 for 循环来解决问题。
解法还是很巧妙地，尤其是 pow这个变量的应用。
Anyway, Good luck, Richardo! -- 08/27/2016
