C ++中没有连续整数的非负整数
假设我们有一个正整数n。我们必须找到小于或等于n的非负整数。约束条件是二进制表示将不包含连续的表示。因此，如果输入为7，则答案将为5，因为5的二进制表示形式为101。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数convert()，将花费n，
ret：=空字符串
当n不为零时，执行-
ret：=ret+（nmod2）
n：=右移n，1次
返回ret
从主要方法中，执行以下操作-
位：=调用函数convert(num)
n：=位数
定义大小为n的数组，定义大小为n的数组零
一个[0]：=1，零[0]：=1
对于初始化i：=1，当i<n时，更新（将i增加1），-
zeroes[i]：=零[i-1]+一个[i-1]
一个[i]：=零[i-1]
ret：=个[n-1]+零[n-1]
对于初始化i：=n-2，当i>=0时，更新（将i减1），执行-
从循环中出来
ret：=ret-个[i]
如果bits[i]与'0'相同且bits[i+1]与'0'相同，则-
否则，当bits[i]与'1'相同且bits[i+1]与'1'相同时，则-
返回ret
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string convert(int n){
string ret = "";
while(n){
ret += (n % 2) + '0';
n >>= 1;
}
return ret;
}
int findIntegers(int num) {
string bits = convert(num);
int n = bits.size();
vector <int> ones(n);
vector <int> zeroes(n);
ones[0] = zeroes[0] = 1;
for(int i = 1; i < n; i++){
zeroes[i] = zeroes[i - 1] + ones[i - 1];
ones[i] = zeroes[i - 1];
}
int ret = ones[n - 1] + zeroes[n - 1];
for(int i = n - 2; i >= 0; i--){
if(bits[i] == '0' && bits[i + 1] == '0') ret -= ones[i];
else if(bits[i] == '1' && bits[i + 1]== '1') break;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.findIntegers(7));
}输入值
7
输出结果
5