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祭衩，試著找規(guī)律灶体，畫了這么一幅圖。
FullSizeRender.jpg
但愚蠢的是掐暮，我只找到了表面上的規(guī)律蝎抽，嘗試著寫出來，發(fā)現(xiàn)很煩路克。
于是看答案樟结。
reference:
https://discuss.leetcode.com/topic/41785/simple-java-o-n-solution-using-two-pointers
發(fā)現(xiàn)
[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]
...
然后就可以寫一個(gè) for 循環(huán)來解決問題。
解法還是很巧妙地精算，尤其是 pow這個(gè)變量的應(yīng)用瓢宦。
Anyway, Good luck, Richardo! -- 08/27/2016
