Flip String to Monotone Increasing trong C++

Chuỗi '0'/'1' gọi là monotone increasing nếu gồm một số '0' (có thể 0) theo sau bởi một số '1' (có thể 0). Cho chuỗi S, có thể flip '0'↔'1'. Tìm số flip tối thiểu để S monotone increasing.

Ví dụ: "010110" → 2 (thành "011111" hoặc "000111").

Giải pháp O(n) một lần duyệt:

• flipCount=0, oneCount=0

• Duyệt S:
  Nếu '0': nếu oneCount>0 thì flipCount++
  Nếu '1': oneCount++
  flipCount = min(flipCount, oneCount)

• Trả về flipCount

Ý tưởng: oneCount là số '1' đã thấy, flipCount là số '0' sau '1' cần flip. Tối thiểu hóa bằng cách chọn flip '1' thành '0' khi oneCount < flipCount.

Ví dụ

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int minFlipsMonoIncr(string S) {       int n = S.size(), flipCount = 0, 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;    } }; int main(){ Solution ob; cout << ob.minFlipsMonoIncr("010110"); }

Đầu vào

"010110"

Đầu ra

2