Pariti dalam bilangan huruf dengan kedudukan huruf yang sama dan pariti frekuensi

Dalam soalan ini kita akan mengira bilangan aksara dengan pariti yang sama dalam kekerapan dan kedudukan dan mencetak kiraan nombor itu sebagai ganjil atau genap.

Untuk menyelesaikan masalah ini, kita boleh mencari kekerapan setiap aksara dalam rentetan dan mengira jumlah bilangan aksara dengan pariti yang sama dalam kekerapan dan kedudukan. Selepas itu kita boleh mencetak jawapan ganjil atau genap berdasarkan kiraan.

Pernyataan Masalah - Kami diberi rentetan alfa yang mengandungi hanya huruf kecil abjad Inggeris. Kita perlu menyemak sama ada bilangan aksara dengan kedudukan dan kekerapan huruf yang sama adalah ganjil atau genap.

Jika mana-mana watak memenuhi mana-mana syarat berikut, maka watak itu mempunyai pariti kekerapan dan kedudukan huruf yang sama.

• Jika kekerapan aksara dalam rentetan adalah ganjil dan kedudukan huruf juga ganjil.

• Jika kekerapan aksara dalam rentetan adalah sekata dan kedudukan huruf juga sekata.

Contoh

Masuk

alpha = "dbbabcdc"

Output

Even

Arahan

• a mempunyai kekerapan 1 dan kedudukan 1, jadi pariti adalah sama dan kiraan menjadi 1.

• d mempunyai kekerapan 2 dan kedudukan 4. Oleh itu, oleh kerana bit pariti adalah sama, kiraan menjadi 2.

Nilai kiraan ialah 2, iaitu nombor genap.

Masuk

alpha = "ppqqr"

Output

Odd

Penjelasan – Hanya pariti ‘p’ sahaja yang sama. Oleh itu, kiraan ialah 1 dan jawapannya ialah nombor ganjil.

Masuk

alpha = "pqqqqrrr";

Output

Even

Nota - Pariti tidak sama untuk mana-mana watak. Oleh itu, memandangkan nilai kiraan adalah sifar, ia mencetak "Genap".

Kaedah 1

Dalam kaedah ini kita akan menggunakan struktur data peta untuk menyimpan kekerapan setiap aksara rentetan. Selepas itu, kami mengira bilangan aksara dengan pariti yang sama dalam kedudukan dan kekerapan huruf.

Algoritma

Langkah 1 - Tentukan tatasusunan kiraan[] panjang 27 dan mulakan dengan 0. Selain itu, mulakan "pariti" dengan 0.

Langkah 2 - Simpan frekuensi aksara dalam tatasusunan count[].

Langkah 3 - Buat 26 lelaran untuk melalui setiap aksara abjad huruf kecil.

Langkah 4 - Jika kiraan[p] lebih besar daripada 0, semak sama ada kekerapan dan kedudukan aksara mempunyai pariti yang sama. Jika ya, tingkatkan nilai Pariti sebanyak 1.

Langkah 5 - Akhir sekali, jika pariti boleh dibahagi dengan 2, kembalikan "Genap". Jika tidak, kembalikan "ganjil".

Contoh

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

string getParity(string alpha) {
    // To store the count of characters
    int count[27] = {0};
    int parity = 0;
    // Count frequency of each character
    for (int p = 0; p < alpha.size(); p++) {
        count[alpha[p] - 'a' + 1]++;
    }
    for (int p = 1; p <= 26; p++) {
        if (count[p] != 0) {
            // Increment parity for valid odd and even parity
            if (p % 2 == 0 && count[p] % 2 == 0 || p % 2 == 1 && count[p] % 2 == 1)
                parity++;
        }
    }
    // Return value based on final parity count
    if (parity % 2 == 1)
        return "ODD";
    else
        return "EVEN";
}
int main() {
    string alpha = "dbbabcdc";
    cout << "The parity of given string's character's is " << getParity(alpha);
    return 0;
}

Output

The parity of given string's character's is EVEN

Kerumitan masa - O(N) untuk mengira kekerapan aksara.

Kerumitan ruang - O(26) ~ O(1) untuk menyimpan kekerapan aksara abjad.

Kaedah 2

Dalam kaedah ini kita akan menyusun rentetan yang diberikan. Selepas itu, apabila kami mendapat aksara bersebelahan yang berbeza, kami menyemak kekerapan dan pariti kedudukan watak sebelumnya.

Algoritma

Langkah 1 - Mulakan "Pariti" kepada 0.

Langkah 2 - kaedah sort() digunakan untuk mengisih rentetan yang diberikan.

Langkah 3 - Mula melintasi rentetan dan mulakan 'charCnt' kepada 0 untuk menyimpan kekerapan aksara semasa.

Langkah 4 - Jika watak semasa berbeza daripada watak seterusnya, semak sama ada pariti dan kedudukan watak "charCnt" sepadan. Jika ya, tingkatkan Pariti sebanyak 1.

Langkah 5 - Jika watak semasa adalah sama dengan watak sebelumnya, tambah "charCnt" sebanyak 1.

Langkah 6 - Akhir sekali, jika nilai "Pariti" genap, kembalikan "Genap". Jika tidak, kembalikan "ganjil".

Contoh

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

string getParity(string alpha) {
    int parity = 0;
    // Sort the string
    sort(alpha.begin(), alpha.end());
    // Traverse the string
    for (int p = 0; p < alpha.size(); p++) {
        int charCnt = 0;        
        // When we get different adjacent characters
        if (alpha[p] != alpha[p + 1]) {
            // Validating the odd and even parties
            if (charCnt % 2 == 1 && (alpha[p] - 'a' + 1) % 2 == 1 || charCnt % 2 == 0 && (alpha[p] - 'a' + 1) % 2 == 0)
                parity++;
        } else {
            charCnt++;
        }
    }
    if (parity % 2 == 1)
        return "ODD";
    else
        return "EVEN";
}
int main() {
    string alpha = "abbbccdd";
    cout << "The parity of given string's character's is " << getParity(alpha);
    return 0;
}

Output

The parity of given string's character's is EVEN

Kerumitan masa - O(NlogN) untuk menyusun rentetan.

Kerumitan ruang - O(N) untuk mengisih rentetan.

Kaedah pertama mengambil ruang yang tetap manakala kaedah kedua mengambil ruang dinamik untuk mengisih rentetan yang diberikan. Di samping itu, kaedah kedua mempunyai kos masa yang lebih tinggi, jadi disyorkan untuk menggunakan kaedah pertama untuk prestasi yang lebih baik.

Atas ialah kandungan terperinci Pariti dalam bilangan huruf dengan kedudukan huruf yang sama dan pariti frekuensi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!