Непрерывный х нет. A, а затем после (nx) no.s of B

Question

Я застрял в одной из связанных с проблемой строк в C ++. Моя логика c хорошо работала для некоторых тестовых случаев, но не для всех тестовых. Пожалуйста, предложите мне действительную логику c следующего вопроса: *

Мне дана строка s из n символов, состоящая только из букв A и B. Я могу выбрать любой индекс i и изменить s (i) на A или B. Найти минимальное нет. Из изменений, которые необходимо внести в строку S, чтобы полученная строка имела формат: AAAAA ..... BBBBB. Другими словами, ваша задача - определить минимум нет. изменений, так что строка s имеет х нет. из А в начале, а затем оставшиеся (nx) нет. из B.

мой код ::

#include<bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, i, flag = 0;
        cin >> n;
        string str;
        cin >> str;
        int cnt = 0, cnt1 = 0;

        for (i = 0; i < str.length(); i++) {
            if (str[i] == 'A') {
                cnt++;
            } else {
                cnt1++;
            }
        }
        int pp = 0;

        //cout << cnt << " " <<cnt1;
        for (i = 0; i < cnt; i++) {
            if (str[i] == 'B') {
                pp++;
            }
        }

        for (i = cnt; i < n; i++) {

            if (str[i] == 'A' && str[i - 1] != 'A') {
                pp++;
            }
        }
        cout << pp << endl;

     }

 }

Например: AAB = 0 изменений, BABA = 2 изменения, AABAA = 1 изменение

Как ответить на этот вопрос , Отвечай !!!

Answer 1

Решение можно найти в простом l oop с учетом процесса с двумя состояниями.

Состояние соответствует тому факту, что для данного индекса мы решаем быть в части А или части В. Переход из состояния B в состояние A не допускается.

Соответствующее число изменений до индекса i может быть затем вычислено итеративно.

Для индекса i, давайте назовем countA[i] количество изменений, чтобы получить A только до индекса i, и давайте назовем countB[i] оптимальным числом изменений вплоть до i, предполагая, что где-то до i или i времени мы решили, что следующая часть последней строки будет содержать только B.

Если текущий символ s[i] равен A, тогда

countA[i] = countA[i-1]
countB[i] = countB[i-1] + 1

Если текущий символ B, то

countA[i] = countA[i-1] + 1
countB[i] = min (countB[i-1], countA[i-1]) 

, если последнее уравнение countB[i] = countB[i-1] соответствует случаю, когда переход в состояние B уже происходит, а countB[i] = countA[i-1] соответствует случаю, когда переход происходит сейчас.

На практике нам не нужен массив для обновления countA и countB.

Вот код:

#include    <iostream>
#include    <string>

int nb_changes (const std::string &s) {
    int n = s.size();
    if (n < 2) return 0;
    int countA = 0, countB = 0;

    for (int i = 0; i < n; ++i) {
        if (s[i] == 'A') {
            countB++;
        } else {
            countB = std::min (countA, countB);
            countA++;
        }
    }
    return std::min (countA, countB);
}

int main() {
    std::string s;

    s = "AAB";
    std::cout  << "number of changes for " << s << " is " << nb_changes(s) << "\n";
    s = "BABA";
    std::cout  << "number of changes for " << s << " is " << nb_changes(s) << "\n";
    s = "AABAA";
    std::cout  << "number of changes for " << s << " is " << nb_changes(s) << "\n";
}

Answer 2

Я написал следующий код для вычисления количества изменений, необходимых для упорядочения строки, содержащей неупорядоченный A e B, в соответствии с порядком, который должен быть «A [... A] B [... B]». (функция countChanges).

Алгоритм (countChanges), используемый для подсчета изменений, действует в три этапа:

• Шаг 1: подсчитывает, сколько «A» символы в строке (cnt).

• Шаг 2: сканирует, сколько символов 'B' есть в первых cnt символах строки, увеличивая счетчик (sum) для каждого обнаруженного «B».

• Шаг 3: сканирует, сколько символов «A» осталось в оставшихся символах строки после 2-го шага, увеличив счетчик (sum ) для каждого обнаруженного «A».

В конце функции sum - ожидаемый результат.

Код также вычисляет и выполняет минимальное число свопы, необходимые для получения строки, упорядоченной в соответствии с требованием.

Код содержит две функции оценки (код под main):

• cntChanges. Он вычисляет необходимое количество изменений (код дает результат как foreseen changes).

• executeSwaps. Он выполняет обмен строк, подсчитывает их и может отображать или не отображать выполненные шаги.

Результат кода:

Do you have a code composed of A and B? [y]es/[n]o/[I] do it/[q]uit y
Insert your code? BABA
Do you want to print swap steps? [y]es/[n]o y

Input: BABA
Step 1 BABA swap(3,0) ==> AABB
Result AABB performed with 1 swap  - foreseen changes 2

-

Do you have a code composed of A and B? [y]es/[n]o/[I] do it/[q]uit n
How much codes do you want to generate? 5
What's your preferred length for all generated codes? 10
Do you want to print swap steps? [y]es/[n]o y

Input: AAAAABAABB
Step 1 AAAAABAABB swap(7,5) ==> AAAAAAABBB
Result AAAAAAABBB performed with 1 swap  - foreseen changes 2
--
Input: ABBABAAABA
Step 1 ABBABAAABA swap(9,1) ==> AABABAAABB
Step 2 AABABAAABB swap(7,2) ==> AAAABAABBB
Step 3 AAAABAABBB swap(6,4) ==> AAAAAABBBB
Result AAAAAABBBB performed with 3 swaps  - foreseen changes 6
--
Input: AAABBAABBB
Step 1 AAABBAABBB swap(6,3) ==> AAAABABBBB
Step 2 AAAABABBBB swap(5,4) ==> AAAAABBBBB
Result AAAAABBBBB performed with 2 swaps  - foreseen changes 4
--
Input: BABAABBABB
Step 1 BABAABBABB swap(7,0) ==> AABAABBBBB
Step 2 AABAABBBBB swap(4,2) ==> AAAABBBBBB
Result AAAABBBBBB performed with 2 swaps  - foreseen changes 4
--
Input: AAABAABAAA
Step 1 AAABAABAAA swap(9,3) ==> AAAAAABAAB
Step 2 AAAAAABAAB swap(8,6) ==> AAAAAAAABB
Result AAAAAAAABB performed with 2 swaps  - foreseen changes 4

-

Код:

#include <iostream>
#include <ctime>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

unsigned int executeSwaps(string &x, bool printSteps);    
unsigned int cntChanges(const string& x);

unsigned int cntChangesJarod42(string const &x);
unsigned int cntChangesDamien(string const &x);

void questionToStart(int &c, size_t &cl, char &ync, char &ynps, string &x);
string generateCode(size_t n);

const char char1='A';
const char char2='B';

int main(void)
{
    srand(static_cast<unsigned int>(time(nullptr)));

    int c;
    size_t cl;
    char ync='n';
    char ynps='n';
    string x;

    x.clear();

    do {
       questionToStart(c,cl,ync,ynps,x);
       if (ync == 'q')
            break;

       for(int i=0;i<c;i++) {
           unsigned int cnt=0;

           if (ync=='n') {
               x=generateCode(cl)
           }

           /* unsigned int fc2 = cntChangesJarod42(x);
           unsigned int fc1 = cntChangesDamien(x);*/

           unsigned int fc3 = cntChanges(x);

           cout << "Input: " << x << endl;
           cnt=executeSwaps(x, (ynps=='y')?1:0);
           cout << "Result " << x << " performed with "
                << ((cnt>0)?to_string(cnt):"no")
                << " swap"
                << ((cnt>1)?"s ":" ") << " - foreseen changes " << fc3 << endl << "--" << endl; 
           /*   << "foreseen changes (@Damien) " << fc1
                << " - foreseen changes (@Jarod42) " << fc2
                << endl << endl;*/
        }
    } while(ync != 'q');

    return 0;
}

unsigned int cntChanges(const string& x)
{
    const char * s;
    unsigned int cnt=0,sum=0,i;

    if (x.empty())
        return 0;

    s=x.c_str();i=0;
    // count char1
    while(*(s+i))
        if (*(s+i++) == char1)
            cnt++;

    /* verify how much elements, from start to cnt,
     *  are different than char1 (equal to char2).
     */
    for(i=0;i<cnt;i++)
        if (*(s+i)==char2)
            sum++;

    cnt=static_cast<unsigned int>(strlen(s));

    /* verify how much of the remaining elements
     *  are different than char2 (equal to char1).
     */
    for(;i<cnt;i++)
        if (*(s+i)==char1)
            sum++;

    return sum;
}

// @Jarod42
unsigned int cntChangesJarod42(const string& s)
{
    if (s.empty()) { return 0; }

    std::vector<std::size_t> switch_count(s.size());

    { // Count 'B' before index
        unsigned int sum = 0;
        std::size_t i = 0;
        for (auto c : s) {
            switch_count[i++] += sum;
            sum += c == 'B';
        }
    }
    { // Count 'A' after the index
        unsigned int sum = 0;
        std::size_t i = 0;
        for (auto c : std::string(s.rbegin(), s.rend())) {
            switch_count[s.size() - 1 - i++] += sum;
            sum += c == 'A';
        }
    }

    return static_cast<unsigned int>(*std::min_element(switch_count.begin(), switch_count.end()));
}

// @Damien Algorithm
unsigned int cntChangesDamien (string const &x)
{
    size_t n = x.length();
    int cntCh_1 = 0, cntCh_2 = 0;

    // there's nothing to swap!! :p
    if (n < 2)
        return 0;

    for (size_t i = 0; i < n; ++i) {
        if (x.at(i) == char1) {
            cntCh_1++;
        } else {
            // x.at(i) is equal to char1

            cntCh_1 = min (cntCh_2, cntCh_1);
            // Now the foreseen swap are equal to cntCh1

            cntCh_2++;
        }
    }


    return static_cast<unsigned int>(std::min (cntCh_2, cntCh_1));
}

unsigned int executeSwaps(string &x, bool printSteps)
{
    unsigned int cnt =0;
    size_t apos=0;
    size_t bpos=0;

    // cout << "Start: " << x << " " << apos << " " << bpos << endl;
    do {
        apos=x.find_last_of(char1);
        if (apos == string::npos)
            break;

        bpos=x.find_first_of(char2);
        if (bpos == string::npos)
            break;

        if (apos>bpos) {
            ++cnt;
            if (printSteps) {
                cout << "Step " << cnt << " " << x << " swap(" << apos << "," << bpos <<") ==> ";
            }
            x.at(bpos)=char1;
            x.at(apos)=char2;

            if (printSteps)
                cout << x << endl;
        }
    } while(apos>bpos);

    return cnt;
}

string generateCode(size_t n)
{
    string x;

    x.clear();

    size_t i,cb=0;
    char ch;
    if (n==0) {
        n=rand()%10;
    }

    for (i=0;i<n-1;i++) {

        ch = ( char1 + (rand()&1) );
        if (ch == char2 )
            cb++;

        x +=ch;
    }

    if (cb==n-1) {
        ch=char1;
    } else if (cb==0) {
        ch=char2;
    } else {
        ch=( char1 + (rand()&1) );
    }
    x += ch;

    return x;
}


void questionToStart(int &c, size_t &cl, char &ync, char &ynps, string &x)
{
    int ex=1;

    do {
        ex=1;
        cout << "Do you have a code composed of "<<char1 << " and " << char2 <<"? [y]es/[n]o/[I] do it/[q]uit ";
        cin >> ync;

        switch(ync) {
        case 'n':
            cout << "How much codes do you want to generate? ";
            cin >> c;
            cout << "What's your preferred length for all generated codes? ";
            cin >> cl;
            break;

        case 'I':
            c=10; cl=(rand()&7)+9;
            cout << c <<" attempts with " << cl << " characters long strings will be executed" << endl;
            break;

        case 'y':
            c=1;
            cout << "Insert your code? ";
            cin >> x;
            cl = x.length();
            break;

        case 'q':
            break;

        default:
            ex=0;
        }
    } while(!ex);


    if ( ync != 'q' ) {
        if ( ync != 'I' ) {
            cout << "Do you want to print swap steps? [y]es/[n]o ";
            cin >> ynps;
        } else {
            ynps = 'y';
            ync = 'n';
        }

        cout << endl;
    }

}

Answer 3

По состоянию на Tfry,

вы можете посчитать количество коммутаторов, необходимое для

• XBBB
• AXBB
• AAXB
• AAAX

, который представляет собой число «B» перед индексом + номер «A» после индекса.

Затем возьмите минимум:

std::size_t count_switch_for_ab(const std::string& s)
{
    if (s.empty()) { return 0; }

    std::vector<std::size_t> switch_count(s.size());

    { // Count 'B' before index
        int sum = 0;
        std::size_t i = 0;
        for (auto c : s) {
            switch_count[i++] += sum;
            sum += c == 'B';
        }
    }
    { // Count 'A' after the index
        int sum = 0;
        std::size_t i = 0;
        for (auto c : std::string(s.rbegin(), s.rend())) {
            switch_count[s.size() - 1 - i++] += sum;
            sum += c == 'A';
        }
    }
    return *std::min_element(switch_count.begin(), switch_count.end());
}

Демо .