คำชี้แจงปัญหา
ให้สตริงไบนารีที่เราสามารถพลิก 1 ทั้งหมดในส่วนด้านซ้ายและ 0 ทั้งหมดในส่วนด้านขวา งานคือการคำนวณการพลิกขั้นต่ำที่จำเป็นในการทำให้ 1 ทั้งหมดอยู่ทางซ้ายและ 0 ทั้งหมดอยู่ทางขวา
ตัวอย่าง
สตริงไบนารีที่กำหนดคือ 0010101 ในสตริงนี้มี 3 1 บิตและ 4 0 บิต เราต้องพลิกไฮไลต์ 4 บิตเพื่อให้ 1 ทั้งหมดอยู่ทางซ้ายและ 0 ทั้งหมดอยู่ทางขวาดังที่แสดงด้านล่าง -
0010101
หลังจากพลิกสตริงจะกลายเป็น −
1110000
อัลกอริทึม
- สำรวจสตริงจากซ้ายไปขวาและคำนวณจำนวนการพลิกที่ต้องการเพื่อแปลงค่า 0 เป็น 1 ทั้งหมด
- สำรวจสตริงจากขวาไปซ้ายและคำนวณจำนวนการพลิกที่จำเป็นเพื่อปกปิดทั้งหมด 1 ถึง 0
- สำรวจตำแหน่งทั้งหมดระหว่างบิตและค้นหาค่าที่น้อยที่สุดของการพลิก (พลิกของ 0 + การพลิก 1 ของ)
ตัวอย่าง
#include <iostream>
#include <string>
#include <climits>
using namespace std;
int minFlips(string binaryString) {
int n = binaryString.length();
int flipCnt, zeroFlips[n], oneFlips[n];
flipCnt = 0;
for (int i = 0; i < n; ++i) {
if (binaryString[i] == '0') {
++flipCnt;
}
zeroFlips[i] = flipCnt;
}
flipCnt = 0;
for (int i = n - 1; i >= 0; --i) {
if (binaryString[i] == '1') {
++flipCnt;
}
oneFlips[i] = flipCnt;
}
int minFlips = INT_MAX;
for (int i = 1; i < n; ++i) {
int sum = zeroFlips[i - 1] + oneFlips[i]; if (sum < minFlips) {
minFlips = sum;
}
}
return minFlips;
}
int main() {
string binaryString = "0010101";
cout << "Minimum flips: " << minFlips(binaryString) <<
endl;
return 0;
} ผลลัพธ์
เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
Minimum flips: 4
