Total Accepted:
76419
Total Submissions:
125855
Difficulty: Medium
Contributor: LeetCode
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.
关键是位运算 自己的low鸡写法
public class Solution {
public int[]
countBits(
int num) {
int[] res =
new int[num+
1];
res[
0] =
0;
if(num==
0)
return res;
res[
1] =
1;
if(num==
1)
return res;
for(
int i=
1; i<=
32;i++){
int offset =
1 << i;
for(
int j= offset; j<
1 << i+
1; j++){
res[j] = res[j-offset]+
1;
if(j==num)
return res;
}
}
return res;
}
}
发现可以通过移位来做，公式为：
f[i]=f[i/2]+i%2.
public int[]
countBits(
int num) {
int[] f =
new int[num +
1];
for (
int i=
1; i<=num; i++) f[i] = f[i >>
1] + (i &
1);
return f;
}
