C ++中没有连续整数的非负整数

假设我们有一个正整数n。我们必须找到小于或等于n的非负整数。约束条件是二进制表示将不包含连续的表示。因此，如果输入为7，则答案将为5，因为5的二进制表示形式为101。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数convert()，将花费n，

• ret：=空字符串

• 当n不为零时，执行-

• ret：= ret +（n mod 2）

• 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