Kira setiap aksara huruf kecil dalam setiap awalan panjang 1 hingga N selepas melakukan operasi yang diterangkan

Dalam masalah ini, kita perlu melakukan operasi yang diberikan untuk setiap awalan rentetan. Akhir sekali, kita perlu mengira kekerapan setiap watak.

Kita boleh menggunakan algoritma tamak untuk menyelesaikan masalah ini. Kita perlu mengambil setiap awalan panjang K dan mengemas kini aksaranya mengikut syarat yang diberikan. Kita boleh menggunakan peta untuk mengira kekerapan aksara dalam rentetan akhir.

Pernyataan Masalah - Kami diberi rentetan tr yang mengandungi N aksara abjad huruf kecil. Selain itu, kami diberikan senarai pemetaan, yang mengandungi sejumlah 26 elemen. Setiap elemen dipetakan kepada aksara huruf kecil berdasarkan nilainya. Contohnya, memetakan[0] memetakan ke "a", memetakan[1] memetakan ke "b", dan memetakan[25] memetakan ke "z". Selain itu, tatasusunan yang dipetakan mengandungi 1 atau -1.

Kita perlu melakukan perkara berikut.

• Dapatkan aksara maksimum daripada awalan panjang K dan dapatkan nilai pemetaan daripada tatasusunan 'pemetaan'.

• Jika nilai yang dipetakan ialah 1, tambahkan semua unsur awalan sebanyak 1.

• Jika nilai yang dipetakan ialah -1, kurangkan semua unsur awalan dengan 1.

Di sini, menambah elemen bermaksud 'a' −> 'b', 'b' −>

Maksud unsur menurun, ‘a’->‘z’, ‘b’->‘a’,…. 'z'->'y'.

Kita perlu melakukan perkara di atas untuk setiap awalan panjang 1

Contoh Contoh

Masuk

mapping = {-1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1}, S = ‘progress’

Output

0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 2 2 1 0 0 0 0 0 0 0 0

Arahan

• Dalam awalan panjang 1, aksara terbesar ialah 'p', yang dipetakan kepada -1. Oleh itu, rentetan yang dikemas kini akan menjadi 'orogress'.

• Dalam awalan panjang 2, aksara maksimum ialah 'r' dan pemetaan ialah -1. Oleh itu, rentetan yang dikemas kini akan menjadi "nqogress".

• Dalam awalan panjang 3, aksara terbesar ialah 'q' dan nilai pemetaan ialah 1. Oleh itu, rentetan yang dikemas kini ialah 'orpgress'.

• Apabila kita selesai dengan segala-galanya, rentetan akhir akan menjadi 'pqmfpdqr' yang mengandungi 1 'f', 2 'p', 2 'q', 1 'm', 1 'd' dan 1 'd' 'r '. Dalam output, kami mencetak kekerapan setiap aksara dalam rentetan yang dihasilkan.

Masuk

mapping = {-1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1}, S = "ab", 

Output

1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Penjelasan− Selepas melakukan semua operasi, rentetan akhir ialah 'ac' dan kami mencetak kekerapan setiap aksara.

Kaedah 1

Dalam kaedah ini, kita akan berulang melalui rentetan dan mengambil nilai K sama dengan indeks P. Selepas itu, kami akan mengambil awalan dengan panjang sama dengan P, mencari aksara terbesar, mengambil nilai yang dipetakan dan mengemas kini semua aksara awalan dengan sewajarnya.

Algoritma

Langkah 1 − Takrifkan pembolehubah 'max_char' untuk menyimpan aksara maksimum bagi awalan yang diberikan.

Langkah 2 − Begitu juga, mulakan senarai panjang 26 dengan sifar untuk menyimpan kekerapan setiap aksara dalam rentetan akhir.

Langkah 3- Mulakan gelung melalui rentetan dan mulakan pembolehubah "max_char" dengan 96 di dalam gelung.

Langkah 4- Cari aksara maksimum daripada awalan panjang p menggunakan gelung bersarang.

Langkah 5 - Kemas kini setiap aksara awalan dengan menambahkan nilai max_char yang dipetakan.

Langkah 7- Jika aksara yang dikemas kini kurang daripada "a", kemas kini kepada "z".

Langkah 8- Jika aksara yang dikemas kini lebih besar daripada "z", kemas kini kepada "a".

Langkah 9− Akhir sekali, simpan kekerapan setiap aksara dalam senarai dengan menggelung pada rentetan yang dikemas kini.

Langkah 10- Cetak kekerapan aksara.

Contoh

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

void performOperations(string &str, vector<int> &mapping) {
    int len = str.length();
    char max_char;
    //  array to store the final frequency of each character
    int freq[26] = {0};
    for (int p = 0; p < len; p++) {
        max_char = 96;
        // Get the maximum character from the prefix string
        for (int q = 0; q <= p; q++) {
            max_char = max(max_char, str[q]);
        }
        // Update the prefix string by adding the max character's value.
        for (int q = 0; q <= p; q++) {
            // adding the mapping value to the current character
            str[q] += mapping[max_char - 'a'];
            // If the updated value is greater than z or less than a, update it
            if (str[q] < 'a') {
                str[q] = 'z';
            } else if (str[q] > 'z') {
                str[q] = 'a';
            }
        }
    }
    // Counting frequency of each character
    for (int p = 0; p < len; p++) {
        freq[str[p] - 'a']++;
    }
    // print count of each character in the updated string
    for (auto ch : freq) {
        cout << ch << ' ';
    }
}
int main() {
    string S = "progress";
    vector<int> mapping = {-1, 1, 1, -1, 1, 1, -1, -1,
                           -1, 1, 1, 1, -1, 1, -1, 1, -1,
                           1, -1, 1, 1, 1, -1, 1, 1, 1};
    performOperations(S, mapping);
    return 0;
}

Output

0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 2 2 1 0 0 0 0 0 0 0 0

Kerumitan masa− O(N*N) kerana kami menggunakan dua gelung bersarang untuk melintasi rentetan.

Kerumitan ruang− O(1) kerana kami menggunakan ruang tetap untuk menyimpan kekerapan aksara.

Kesimpulan

Kami melakukan operasi yang diberikan pada rentetan input dan mencetak kekerapan aksara rentetan yang dikemas kini dalam output. Pengaturcara juga boleh menggunakan peta dalam C++ untuk menyimpan frekuensi aksara dan bukannya menggunakan senarai. Untuk lebih banyak latihan, pengaturcara boleh cuba mencetak kekerapan terkumpul setiap aksara dalam rentetan yang dikemas kini.

Atas ialah kandungan terperinci Kira setiap aksara huruf kecil dalam setiap awalan panjang 1 hingga N selepas melakukan operasi yang diterangkan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!