สมมติว่าคุณกำหนดสตริงไบนารี "10011" ในการสร้างสตริงไบนารีสำรอง เราต้องพลิกอักขระอย่างน้อย 2 ตัวเป็น "10101"
มีความเป็นไปได้สองอย่างสำหรับสตริงสำรอง จะเริ่มต้นด้วย 0 หรือ 1 เราจะตรวจสอบทางเลือกสองทางและนับจำนวนการพลิกที่จำเป็นสำหรับทั้งคู่
แล้วคืนค่าต่ำสุดของทั้งสอง มาดูตัวอย่างกัน
ป้อนข้อมูล
binary = "10011"
ผลผลิต
2
หากเราเริ่มสตริงด้วย 0 เราต้องพลิก 3 ครั้ง และถ้าเราเริ่มสตริงด้วย 1 เราก็จะต้องพลิก 2 ครั้ง ขั้นต่ำคือ 2.
อัลกอริทึม
- เริ่มต้นสตริงไบนารี
- นับการพลิกที่จำเป็นเพื่อให้สตริงสลับกันโดยเริ่มจาก 1
- ให้นับการพลิกที่จำเป็นในการสลับสตริงโดยเริ่มจาก 0 ในทำนองเดียวกัน
- หาค่าต่ำสุดจากสองตัวข้างบนนี้
- พิมพ์ข้อความ
การนำไปใช้
ต่อไปนี้เป็นการนำอัลกอริธึมข้างต้นไปใช้ใน 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
