C++で1からNを表すサブ文字列を持つバイナリ文字列

バイナリ文字列Sと正の整数Nがあるとすると、1からNまでのすべての整数Xについて、Xのバイナリ表現が指定されたSの部分文字列である場合にのみ、trueと言わなければなりません。したがって、S =“ 0110 」およびN=3の場合、1、10、および11はすべて0110に存在するため、結果はtrueになります。

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

• nを入力として受け取るconvert（）のメソッドを定義します

• ret：=空の文字列

• nが0ではない場合

  • ret：=ret concatenate n mod 2

  • n：=n / 2

• 逆のretとreturn

• メインの方法から、次のようにします

• i：=Nの場合、i> =N / 2の場合、iを1減らします

  • temp：=convert（i）

  • 温度がSでない場合は、falseを返します

• trueを返します。

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string convert(int n){
      string ret = "";
      while(n){
         ret += (n % 2) + '0';
         n /= 2;
      }
      reverse(ret.begin(), ret.end());
      return ret;
   }
   bool queryString(string S, int N) {
      for(int i = N; i >= N/2; i-- ){
         string temp = convert(i);
         if(S.find(temp) == string::npos) return false;
      }
      return true;
   }
};
main(){
   Solution ob;
   cout << (ob.queryString("0110", 3));
}

入力

"0110"
3

出力

1