题目描述
给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含连续的 1 的个数。
样例
输入: 5
输出: 5
解释:
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。
注意
- 1≤n≤109
算法
(数位统计) O(logn)
- 按照数位统计的一般思路，从二进制的高位向底位，每次保证作为答案的数字不能超过 n。
- 首先预处理出长度为 i 的二进制串中，以 0 作为最高位且符合条件的二进制串的个数。这里从低位开始往高位递推，递推方程为 f(i)=f(i−1)+f(i−2)，其中，f(0)=f(1)=1。f(0) 无具体含义。
- 从高到底遍历 n 的二进制位，设计布尔变量 last_one，表示 n 的二进制位中上一位是否为 1，初始为 false。
- 若第 i 位为 1，累计答案 f(i+1)，然后考察 last_one，若 last_one 为 true，则此时统计工作已经结束，直接返回 ans；否则，设置 last_one = true。
- 若第 i 位为 0，设置 last_one = false。
- 最终返回 ans + 1，这里的加 1 加的是 n 本身作为合法的答案。
下面以例子 10101100 为例分析：
- 第 7 位是 1，则答案累计 f(8)，这里累计的是
00000000 - 01111111的答案个数；此时 last_one = false，然后设置 last_one = true。 - 第 6 位是 0，设置 last_one = false。
- 第 5 位是 1，则答案累计 f(6)，这里累计的是
10000000 - 10011111的答案个数；此时 last_one = false，然后设置 last_one = true - 第 4 位是 0，设置 last_one = false。
- 第 3 位是 1，则答案累计 f(4)，这里累计的是
10100000 - 10100111的答案个数。此时 last_one = false，然后设置 last_one = true。 - 第 2 位是 1，则答案累计 f(3)，这里累计的是
10101000 - 10101011的答案个数。此时 last_one = true，无需再进行之后的统计，因为第 2 位不能放置 1，所以返回答案为 f(3) + f(4) + f(6) + f(8) = 55。
时间复杂度
- 只涉及到对二进制位的操作，故时间复杂度为 O(logn)。
C++ 代码
class Solution {
public:
int findIntegers(int num) {
vector<int> f(31);
f[0] = f[1] = 1;
for (int i = 2; i < 31; i++)
f[i] = f[i - 1] + f[i - 2];
bool last_one = false;
int ans = 0;
for (int i = 29; i >= 0; i--) {
if (num & (1 << i)) {
ans += f[i + 1];
if (last_one)
return ans;
last_one = true;
}
else
last_one = false;
}
return ans + 1;
}
};
相似的想法， 但是用递归实现的。
template <class F> struct recursive { F f; template <class... Ts> decltype(auto) operator()(Ts&&... ts) const { return f(std::ref(*this), std::forward<Ts>(ts)...); } template <class... Ts> decltype(auto) operator()(Ts&&... ts) { return f(std::ref(*this), std::forward<Ts>(ts)...); } }; template <class F> recursive(F) -> recursive<F>; auto const rec = [](auto f){ return recursive{std::move(f)}; }; class Solution { public: int findIntegers(int num) { const vector<int> binary = [&](vector<int> self = {}) { string s = (std::bitset<32>(num)).to_string(); std::transform(begin(s), end(s), std::back_inserter(self), [&](auto &x) { return x - '0'; }); std::reverse(begin(self), end(self)); while(self.back() == 0) self.pop_back(); return self; }(); auto f = rec([&, memo = array<optional<int>, 32> {}](auto &&f, int i) mutable -> int { if (memo[i]) return *memo[i]; return *(memo[i] = [&]{ if (i == 0) return 2; else if (i == 1) return 3; else return f(i - 1) + (i - 2 >= 0 ? f(i - 2) : 0); }()); }); auto g = rec([&, memo = array<optional<int>, 32> {}](auto&& g, int i) mutable -> int { if (memo[i]) return *memo[i]; return *(memo[i] = [&]{ if (i == 0) return binary[i] == 0 ? 1 : 2; else { if (binary[i] == 1 and binary[i - 1] == 0) return f(i - 1) + (i - 2 >= 0 ? g(i - 2) : 1); else if (binary[i] == 1 and binary[i - 1] == 1) return f(i - 1) + (i - 2 >= 0 ? f(i - 2) : 1); else if (binary[i] == 0) return g(i - 1); else throw std::domain_error("unmatched case"); } }()); }); return g(size(binary) - 1); } };