C++で連続するものがない非負の整数

正の整数nがあるとします。 n以下の非負の整数を見つける必要があります。制約は、バイナリ表現に連続した表現が含まれないことです。したがって、入力が7の場合、5のバイナリ表現は101であるため、答えは5になります。

これを解決するには、次の手順に従います-

• 関数convert（）を定義します。これにはnが必要です。
• ret：=空の文字列
• nがゼロ以外の場合、-
  を実行します。
  • ret：=ret +（n mod 2）
  • n：=右シフトn、1回
• return ret
• メインの方法から、次の手順を実行します-
• ビット：=関数convert（num）を呼び出す
• n：=ビットのサイズ
• サイズnの配列0を定義し、サイズnの配列0を定義します
• ones [0]：=1、zeroes [0]：=1
• iを初期化する場合：=1、i
• zeroes [i]：=zeroes [i-1] + ones [i-1]
• ones [i]：=zeroes [i-1]

理解を深めるために、次の実装を見てみましょう-

例

#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