https://www.hrwhisper.me/leetcode-counting-bits/
https://leetcode.com/problems/counting-bits/discuss/79539/Three-Line-Java-Solution
倒过来想，一个数 * 2 就是把它的二进制全部左移一位，也就是说 1的个数是相等的。
https://leetcode.com/discuss/92609/three-line-java-solution
public int[] countBits(int num) { int[] answer = new int[num+1]; int offset = 1; for(int i = 1; i < answer.length; i++){ if(offset * 2 == i) offset *= 2; answer[i] = 1 + answer[i - offset]; } return answer; }
https://leetcode.com/discuss/93807/simple-java-dynamic-programming-without-bitwise-operation
int[] bits = new int[num + 1]; for(int i = 1; i <= num; i++){ bits[i] = bits[i/2]; if(i%2 == 1) bits[i]++; } return bits; }
X. http://www.cnblogs.com/grandyang/p/5294255.html
X. Simple Java O(n) solution using two pointers
https://leetcode.com/problems/counting-bits/discuss/79557/how-we-handle-this-question-on-interview-thinking-process-dp-solution
dp[index] = dp[index - offset] + 1;
http://blog.csdn.net/lnho2015/article/details/50924299
public int[] countBits(int num) { int[] result=new int[num+1]; result[0]=0; for(int i=1;i<=num;i++){ result[i]=getCount(i); } return result; } public int getCount(int num){ int count=0; while(num!=0){ if((num&1)==1){ count++; } num/=2; } return count; }
https://leetcode.com/discuss/92675/handle-this-question-interview-thinking-process-solution
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
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.
Hint:
- You should make use of what you have produced already.
- Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
- Or does the odd/even status of the number help you in calculating the number of 1s?
想一想，当一个数为2的整数幂的时候，1的个数为1，比如2（10) 和4(100)，8(1000)
在这之后就是前一个序列的数+1 比如 9(1001) = 1(1) + 8 (1) = 2
就是把一个数分解为小于它的最大2的整数幂 + x
public int[] countBits(int num) {
int[] res = new int[num+1];
int pow2 = 1,before =1;
for(int i=1;i<=num;i++){
if (i == pow2){
before = res[i] = 1;
pow2 <<= 1;
}
else{
res[i] = res[before] + 1;
before += 1;
}
}
return res;
}
https://leetcode.com/problems/counting-bits/discuss/79539/Three-Line-Java-Solution
An easy recurrence for this problem is 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;
}
那么我们可以利用这个结论来做。
res[i /2] 然后看看最低位是否为1即可（上面*2一定是偶数，这边比如15和14除以2都是7，但是15时通过7左移一位并且+1得到，14则是直接左移）
所以res[i] = res[i >>1] + (i&1)
public int[] countBits(int num) {
int[] res = new int[num+1];
for(int i=1;i<=num;i++){
res[i] = res[i >> 1] + (i & 1);
}
return res;
public int[] countBits(int num) { int[] answer = new int[num+1]; int offset = 1; for(int i = 1; i < answer.length; i++){ if(offset * 2 == i) offset *= 2; answer[i] = 1 + answer[i - offset]; } return answer; }
https://leetcode.com/discuss/93807/simple-java-dynamic-programming-without-bitwise-operation
int[] bits = new int[num + 1]; for(int i = 1; i <= num; i++){ bits[i] = bits[i/2]; if(i%2 == 1) bits[i]++; } return bits; }
X. http://www.cnblogs.com/grandyang/p/5294255.html
下面这种方法就更加巧妙了，巧妙的利用了i&(i - 1)， 这个本来是用来判断一个数是否是2的指数的快捷方法，比如8，二进制位1000, 那么8&(8-1)为0，只要为0就是2的指数, 那么我们现在来看一下0到15的数字和其对应的i&(i - 1)值：
我们可以发现每个i值都是i&(i-1)对应的值加1，这样我们就可以写出代码如下：
vector<int> countBits(int num) { vector<int> res(num + 1, 0); for (int i = 1; i <= num; ++i) { res[i] = res[i & (i - 1)] + 1; } return res; }
这道题给我们一个整数n，然我们统计从0到n每个数的二进制写法的1的个数，存入一个一维数组中返回，题目中明确表示不希望我们一个数字一个数字，一位一位的傻算，而是希望我们找出规律，而且题目中也提示了我们注意[2-3], [4-7], [8-15]这些区间的规律，那么我们写出0到15的数的二进制和1的个数如下：
0 0000 0 ------------- 1 0001 1 ------------- 2 0010 1 3 0011 2 ------------- 4 0100 1 5 0101 2 6 0110 2 7 0111 3 ------------- 8 1000 1 9 1001 2 10 1010 2 11 1011 3 12 1100 2 13 1101 3 14 1110 3 15 1111 4
我最先看出的规律是这样的，除去前两个数字0个1，从2开始，2和3，是[21, 22)区间的，值为1和2。而4到7属于[22, 23)区间的，值为1,2,2,3，前半部分1和2和上一区间相同，2和3是上面的基础上每个数字加1。再看8到15，属于[23, 24)区间的，同样满足上述规律，所以可以写出代码如下：
vector<int> countBits(int num) { if (num == 0) return {0}; vector<int> res{0, 1}; int k = 2, i = 2; while (i <= num) { for (i = pow(2, k - 1); i < pow(2, k); ++i) { if (i > num) break; int t = (pow(2, k) - pow(2, k - 1)) / 2; if (i < pow(2, k - 1) + t) res.push_back(res[i - t]); else res.push_back(res[i - t] + 1); } ++k; } return res; }
X. Simple Java O(n) solution using two pointers
https://leetcode.com/problems/counting-bits/discuss/79615/simple-java-on-solution-using-two-pointers
This uses the hint from the description about using ranges. Basically, the numbers in one range are equal to 1 plus all of the numbers in the ranges before it. If you write out the binary numbers, you can see that numbers 8-15 have the same pattern as 0-7 but with a 1 at the front.
My logic was to copy the previous values (starting at 0) until a power of 2 was hit (new range), at which point we just reset the t pointer back to 0 to begin the new range.
public int[] countBits(int num) {
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;
t = 0;
}
ret[i] = ret[t] + 1;
}
return ret;
} public int[] countBits(int num) {
int[] res = new int[num+1];
res[0] = 0;
for(int i=1,j=0; i < res.length; i++,j++){
if( (i&i-1) == 0){
j=0;
}
res[i] = 1 + res[j];
}
return res;
}https://leetcode.com/problems/counting-bits/discuss/79557/how-we-handle-this-question-on-interview-thinking-process-dp-solution
dp[index] = dp[index - offset] + 1;
public int[] countBits(int num) {
int result[] = new int[num + 1];
int offset = 1;
for (int index = 1; index < num + 1; ++index){
if (offset * 2 == index){
offset *= 2;
}
result[index] = result[index - offset] + 1;
}
return result;
}
There is one imporant observation we can make about the number of bits in each number.
- Each Power of 2 has exactly only 1 bit. (2 : 0010 , 4: 0100, 8:1000, 16:10000)
- Each number after the power of 2 follows a pecular pattern :
0 → 01 → 02 → 1 + dp[0]Nearest Power of 23 → 1 + dp[1]1 greater than nearest4 → 1 + dp[0]Nearest5 → 1+ dp[1]1 greater than nearest6 → 1+ dp[2]2 greater than nearest7 → 1+ dp[3]3 greater than nearest8 → 1+ dp[0]Nearest9 → 1+ dp[1]10 → 1+ dp[2]11 → 1+ dp[3]12 → 1+ dp[4]
You can easily see the pattern here.
class Solution {
public:
//Function to check whether the number is a power of 2 or now
inline bool ispowerof2(int n){
return (n & (n-1)) == 0;
}
vector<int> countBits(int num) {
vector<int> dp(num+1);
dp[0]=0;
if(num>=1)
dp[1]=1;
int curr=2;
int nearest=2;
while(curr<=num)
{
//nearest stores the nearest power of 2 less than current element (nearest of 5 is 4, nearest of 13 is 8..)
nearest = ispowerof2(curr) ? curr : nearest;
dp[curr] = 1 + dp[curr-nearest]; // 1 stands for dp[nearest]
curr++;
}
return dp;
}
};
Just take note of the
bool ispowerof2(n) method here. It uses bit operation to find whether it is power of 2. More tricks here. The reference is here
Inline function is used for small functions which make the function code to be written at the call during compile time. It reduces overhead
https://blog.csdn.net/katrina95/article/details/79118067通过观察发现每到2^n的时候为1，从2^n ~ 2^(n+1)，其结果为0 ~ 2^(n-1)的结果加1，因为相比较而言，就是第一个标志位多了一个1
Brute Force:http://blog.csdn.net/lnho2015/article/details/50924299
public int[] countBits(int num) { int[] result=new int[num+1]; result[0]=0; for(int i=1;i<=num;i++){ result[i]=getCount(i); } return result; } public int getCount(int num){ int count=0; while(num!=0){ if((num&1)==1){ count++; } num/=2; } return count; }
https://leetcode.com/discuss/92675/handle-this-question-interview-thinking-process-solution
