The n
bits in_k
可以解释为小于一个整数的表示2^n
.
这允许轻松使用一维数组(向量)d[.]
.
实际上,一个整数j
对应于
j = in[0] + 2*in[1] + ... + 2^n-1*in[n-1]
而且,直接实现是O(NlogN)。 (N = 2^n)
递归解决方案是可能的,例如使用
f(val, n) = updown(val%2) + f(val/2, n-1) and f(val, 0) = 0.
在引入记忆化的情况下,这对应于 O(N) 复杂度,此处未实现。
Result:
0 : 0
1 : 1
2 : 1
3 : 2
4 : 1
5 : 2
6 : 2
7 : 3
8 : 1
9 : 2
10 : 2
11 : 3
12 : 2
13 : 3
14 : 3
15 : 4
#include <iostream>
#include <vector>
int up_down (int b) {
if (b) return 1;
return 0;
}
int f(int val, int n) {
if (n < 0) return 0;
return up_down (val%2) + f(val/2, n-1);
}
int main() {
const int n = 4;
int size = 1;
for (int i = 0; i < n; ++i) size *= 2;
std::vector<int> d(size, 0);
for (int i = 0; i < size; ++i) {
d[i] = f(i, n);
}
for (int i = 0; i < size; ++i) {
std::cout << i << " : " << d[i] << '\n';
}
return 0;
}
如上所述,在实现记忆化的条件下,递归方法允许 O(N) 复杂度。
另一种可能性是使用简单的迭代方法,以获得 O(N) 复杂度。
(这里N代表数据总数)
#include <iostream>
#include <vector>
int up_down (int b) {
if (b) return 1;
return 0;
}
int main() {
const int n = 4;
int size = 1;
for (int i = 0; i < n; ++i) size *= 2;
std::vector<int> d(size, 0);
int size_block = 1;
for (int i = 0; i < n; ++i) {
for (int j = size_block-1; j >= 0; --j) {
d[2*j+1] = d[j] + up_down(1);
d[2*j] = d[j] + up_down(0);
}
size_block *= 2;
}
for (int i = 0; i < size; ++i) {
std::cout << i << " : " << d[i] << '\n';
}
return 0;
}