Chuỗi nhị phân với chuỗi con biểu diễn từ 1 đến N trong C ++

Giả sử chúng ta có một chuỗi nhị phân S và một số nguyên dương N, chúng ta phải nói đúng nếu và chỉ khi với mọi số nguyên X từ 1 đến N, biểu diễn nhị phân của X là một chuỗi con của S. Vì vậy, nếu S =“0110 ”Và N =3, thì kết quả sẽ là true, vì 1, 10 và 11 đều có trong 0110.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một phương thức để convert (), sẽ lấy n làm đầu vào

• ret:=một chuỗi trống

• trong khi n không phải là 0

  • ret:=ret nối n mod 2

  • n:=n / 2

• đảo ngược ret và trả lại

• Từ phương thức chính, hãy thực hiện như sau

• đối với i:=N, khi i> =N / 2, giảm i đi 1

  • temp:=convert (i)

  • nếu tạm thời không ở S, trả về false

• trả về true.

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

"0110"
3

Đầu ra

1