จำนวนการพลิกบิตเพื่อทำให้สตริงไบนารีสลับกันใน C++

ให้สตริงไบนารี หาจำนวนการพลิก (flip) น้อยที่สุดเพื่อทำให้เป็นสตริงสลับกัน (0101... หรือ 1010...)

ตัวอย่าง:

Input: "10011"
Output: 2

เริ่ม 0 ต้องพลิก 3 ครั้ง, เริ่ม 1 ต้องพลิก 2 ครั้ง → เลือก 2

อัลกอริทึม

• ฟังก์ชัน flip(c) คืนค่าตรงข้าม
• ฟังก์ชันนับ flip เริ่มจาก expected char
• คำนวณทั้งเริ่ม 0 และ 1 取 min

การเขียนโปรแกรม C++

#include <bits/stdc++.h> using namespace std; char flip(char binaryDigit) { return binaryDigit == '0' ? '1' : '0'; } int getFlipCountToAlternateString(string binary, char expected) {    int flipCount = 0;    for (int i = 0; i < binary.length(); i++) {       if (binary[i] != expected) flipCount++;       expected = flip(expected);    }    return flipCount; } int main() {    string binary = "10011";    cout << min(getFlipCountToAlternateString(binary, '0'), getFlipCountToAlternateString(binary, '1')) << endl;    return 0; }

ผลลัพธ์

2