สมมติว่ามีการกำหนดสตริงของ '0' และ '1' สตริงนั้นจะเพิ่มขึ้นแบบโมโนโทนิกหากประกอบด้วยจำนวน '0' (อาจเป็น 0) ตามด้วยจำนวน '1' (อาจเป็น 0 ด้วย) เรามีสตริง S ของ '0' และ '1' และเราอาจพลิก '0' เป็น '1' หรือ '1' เป็น '0' ค้นหาจำนวนการพลิกขั้นต่ำเพื่อให้ S เสียงเดียวเพิ่มขึ้น ดังนั้นหากอินพุตเป็น "010110" เอาต์พุตจะเป็น 2 เมื่อพลิกเราจะได้ "011111" หรือ "000111"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
n :=ขนาดของ S ตั้งค่า flipCount :=0, oneCount :=0
-
สำหรับฉันอยู่ในช่วง 0 ถึง n – 1
-
ถ้า S[i] เป็น 0 แล้ว
-
ถ้า oneCount =0 ให้ข้ามไปที่การวนซ้ำถัดไป
-
เพิ่ม flipCount ขึ้น 1
-
-
มิเช่นนั้นให้เพิ่ม oneCount ขึ้น 1
-
ถ้า oneCount
-
-
ส่งคืน flipCount
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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"));
} อินพุต
"010110"
ผลลัพธ์
2
