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

เราได้รับสตริงที่อาจมี "ab" และงานคือคำนวณจำนวนการดำเนินการที่ต้องใช้เพื่อลบหรือลบ "ab" ออกจากสตริง ดังนั้นงานของเราคือตรวจสอบก่อนว่าสตริงมี "ab" หรือไม่ ถ้ามีต้องทำให้สตริง "ab" free

อินพุต − string str = "ababaa"

เอาต์พุต − จำนวนการดำเนินการเพื่อทำให้สตริงไบนารี "ab" free คือ 4

คำอธิบาย − ตามที่เห็นในสตริง รูปแบบ "ab" เกิดขึ้น 2 ครั้ง เราจะแทนที่ "ab" ด้วย "bba" จำนวนการดำเนินการคือ 1 สตริงกลายเป็น bbaabaa อีกครั้งแทนที่ "ab" ด้วย "bba" จำนวน 2 สตริงกลายเป็น bbabbaaa ยังมี "ab" อีก จำนวน 3 สตริงกลายเป็น bbabbaaa เมื่อเราทำการแทนที่ "ab" ที่ตรวจสอบด้วย "bba" ต่อเนื่อง สตริงจะกลายเป็น "ab" free

อินพุต − str = "abaa"

เอาต์พุต − จำนวนการดำเนินการเพื่อทำให้สตริงไบนารี "ab" free คือ 1

คำอธิบาย − ในสตริง "ab" เกิดขึ้น 1 ครั้ง แทนที่ด้วย "bba" จำนวน 1 สตริงกลายเป็น bbaaa ตอนนี้สตริง "ab" free และจำนวนคือ 1

แนวทางที่ใช้ในโปรแกรม

• รับสตริงและคำนวณความยาว ส่งไปฟังก์ชันประมวลผล
• ประกาศตัวแปรชั่วคราว count เก็บจำนวนการดำเนินการทำให้สตริง "ab" free
• สร้างอาเรย์ตัวอักษรขนาดความยาวสตริง + 1
• เก็บตัวอักษรของสตริงในอาเรย์ด้วย strcpy()
• ลูป FOR จาก 0 ถึงความยาวสตริง
• ในลูป ตรวจสอบถ้า arr[length - i - 1] == 'a' กำหนด count = (count + total) และ total = (total * 2)
• มิฉะนั้น เพิ่ม total 1
• คืนค่า count
• พิมพ์ผลลัพธ์

ตัวอย่างโค้ด C++

#include<bits/stdc++.h>
using namespace std;

int operations_ab_free(string str, int len){
    int count = 0;
    char arr[length + 1];
    strcpy(arr, str.c_str());
    int total = 0;
    for (int i = 0; i < len; i++){
        if (arr[len - i - 1] == 'a'){
            count = (count + total);
            total = (total * 2);
        } else {
            total++;
        }
    }
    return count;
}

int main(){
    string str = "ababaa";
    int length = str.length();
    cout<<"Count of operations to make a binary string \"ab\" free are: "<<operations_ab_free(str, length)<<endl;
    return 0;
}

เอาต์พุต

หากรันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −

Count of operations to make a binary string "ab" free are: 4