Lật chuỗi thành đơn điệu Tăng trong C ++

Giả sử một chuỗi '0 và' 1 được đưa ra. Chuỗi đó sẽ đơn điệu tăng lên nếu nó bao gồm một số số '0 (có thể là 0), tiếp theo là một số' 1 (cũng có thể là 0). Chúng ta có một chuỗi S gồm '0' và '1, và chúng ta có thể chuyển bất kỳ' 0 'nào thành' 1 'hoặc' 1 'thành' 0 '. Tìm số lần lật nhỏ nhất để độ đơn điệu S tăng dần. Vì vậy, nếu đầu vào là “010110”, thì đầu ra sẽ là 2. Bằng cách lật, chúng ta có thể nhận được “011111” hoặc “000111”.

Để 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, đặt flipCount:=0, oneCount:=0

• cho tôi trong phạm vi từ 0 đến n - 1

  • nếu S [i] là 0 thì

    • nếu oneCount =0, thì bỏ qua lần lặp tiếp theo

    • tăng flipCount lên 1

  • nếu không thì hãy tăng oneCount lên 1

  • nếu oneCount

• trả về flipCount

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:
   int minFlipsMonoIncr(string S) {
      int n = S.size();
      int flipCount = 0;
      int oneCount = 0;
      for(int i = 0; i < n; i++){
         if(S[i] == '0'){
            if(oneCount == 0) continue;
            flipCount++;
         } else oneCount++;
            if(oneCount < flipCount) flipCount = oneCount;
      }
      return flipCount;
   }
};
main(){
   Solution ob;
   cout << (ob.minFlipsMonoIncr("010110"));
}

Đầu vào

"010110"

Đầu ra

2