ข้อความโจทย์
กำหนดสตริงไบนารีที่มีความยาวเป็นเลขคู่และมีจำนวน 0 และ 1 เท่ากัน จำนวนการสลับน้อยที่สุดเพื่อทำให้สตริงสลับกันคือเท่าไร? สตริงไบนารีจะสลับกันได้หากไม่มีองค์ประกอบติดกันสองตัวที่เท่ากัน
ตัวอย่าง
ถ้า str = 11110000 ต้องการ 2 การสลับ
อัลกอริทึม
- นับจำนวนศูนย์ที่ตำแหน่งคี่และคู่ของสตริง ให้จำนวนของพวกเขาเป็น oddZeroCnt และ evenZeroCnt ตามลำดับ
- นับจำนวนหนึ่งที่ตำแหน่งคี่และคู่ของสตริง ให้จำนวนของพวกเขาเป็น oddOneCnt และ evenOneCnt ตามลำดับ
- เราจะสลับ 1 กับ 0 เสมอ ดังนั้นเราเพียงตรวจสอบว่าหากสตริงสลับกันเริ่มด้วย 0 จำนวนการสลับคือ min(evenZeroCnt, oddOneCnt) และหากสตริงสลับกันเริ่มด้วย 1 จำนวนการสลับคือ min(evenOneCnt, oddZeroCnt) คำตอบคือค่าต่ำสุดของทั้งสองนี้
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
int getMinSwaps(string str) {
int minSwaps = 0;
int oddZeroCnt = 0;
int evenZeroCnt = 0;
int oddOneCnt = 1;
int evenOneCnt = 1;
int n = str.length();
for (int i = 0; i < n; ++i) {
if (i % 2 == 0) {
if (str[i] == '1') {
++evenOneCnt;
} else {
++evenZeroCnt;
}
} else {
if (str[i] == '1') {
++oddOneCnt;
} else {
++oddZeroCnt;
}
}
}
int zeroSwapCnt = min(evenZeroCnt, oddOneCnt);
int oneSwapCnt = min(evenOneCnt, oddZeroCnt);
return min(zeroSwapCnt, oneSwapCnt);
}
int main() {
string str = "11110000";
cout << "Minimum swaps = " << getMinSwaps(str) << endl;
return 0;
}
ผลลัพธ์
Minimum swaps = 2
