338.Counting Bits¶
Tags: Medium Dynamic Programming Bit Manipulation
Links: https://leetcode.com/problems/counting-bits/
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 1:
Input: 2
Output: [0,1,1]
Example 2:
Input: 5
Output: [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.
解法一：
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，是 [2^1, 2^2) 区间的，值为1和2。而4到7属于 [2^2, 2^3) 区间的，值为 1,2,2,3，前半部分1和2和上一区间相同，2和3是上面的基础上每个数字加1。再看8到 15，属于 [2^3, 2^4) 区间的，同样满足上述规律
class Solution {
public:
vector<int> countBits(int num) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
if (num == 0) return {0};
vector<int> res(num + 1);
res[0] = 0, res[1] = 1;
int k = 1, i = 1 << k;
while (i <= num) {
int left = 1 << k, right = left << 1;
int mid = left + ((right - left) >> 1);
int half = (right - left) >> 1;
while (i < mid) {
if (i > num) return res;
res[i] = res[i - half];
++i;
}
while (i < right) {
if (i > num) return res;
res[i] = res[i - half] + 1;
++i;
}
++k;
}
return res;
}
};
解法二：从1开始，遇到偶数时，其1的个数和该偶数除以2得到的数字的1的个数相同，遇到奇数时，其1的个数等于该奇数除以2得到的数字的1的个数再加1
class Solution {
public:
vector<int> countBits(int num) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<int> res(num + 1);
res[0] = 0;
for (int i = 1; i <= num; ++i) {
if (i & 1) res[i] = res[i >> 1] + 1;
else res[i] = res[i >> 1];
}
return res;
}
};
解法三：巧妙的利用了 i&(i - 1)， 这个本来是用来判断一个数是否是2的指数的快捷方法，比如8，二进制位 1000, 那么 8&(8-1) 为0，只要为0就是2的指数, 那么我们现在来看一下0到 15 的数字和其对应的 i&(i - 1) 值, 每个i值都是 i&(i-1) 对应的值加1
i binary '1' i&(i-1)
0 0000 0
-----------------------
1 0001 1 0000
-----------------------
2 0010 1 0000
3 0011 2 0010
-----------------------
4 0100 1 0000
5 0101 2 0100
6 0110 2 0100
7 0111 3 0110
-----------------------
8 1000 1 0000
9 1001 2 1000
10 1010 2 1000
11 1011 3 1010
12 1100 2 1000
13 1101 3 1100
14 1110 3 1100
15 1111 4 1110
class Solution {
public:
vector<int> countBits(int num) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<int> res(num + 1);
res[0] = 0;
for (int i = 1; i <= num; ++i) {
res[i] = res[i & (i - 1)] + 1;
}
return res;
}
};