Mã C ++ để tìm chuỗi đúng tối thiểu từ chuỗi nhị phân đã cho

Giả sử chúng ta có một chuỗi nhị phân S với n bit. Không có số 0 ở đầu dư thừa. Chúng tôi có thể thực hiện hai hoạt động khác nhau trên S -

• Hoán đổi bất kỳ cặp bit nào liền kề

• Thay thế tất cả "11" bằng "1"

Gọi val (S) là biểu diễn thập phân của S. Chúng ta phải tìm chuỗi đúng nhỏ nhất, trong đó chuỗi đúng A nhỏ hơn chuỗi đúng khác 'B' khi val (A)

Vì vậy, nếu đầu vào là S ="1001", thì đầu ra sẽ là 100, vì chúng ta có thể thực hiện phép toán như "1001" -> "1010" -> "1100" -> "100".

Các bước

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

n := size of S
res := a blank string
res := res + S[0]
for initialize i := 1, when i < n, update (increase i by 1), do:
   if S[i] is same as '0', then:
      res := res concatenate "0"
return res

Ví dụ

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

#include <bits/stdc++.h>
using namespace std;
string solve(string S){
   int n = S.size();
   string res = "";
   res += S[0];
   for (int i = 1; i < n; i++){
      if (S[i] == '0'){
         res += "0";
      }
   }
   return res;
}
int main(){
   string S = "1001";
   cout << solve(S) << endl;
}

Đầu vào

"1001"

Đầu ra

100