Heim > Artikel > Backend-Entwicklung > Minimieren Sie die Anzahl der Neuanordnungen von Zeichen, die alle gegebenen Zeichenfolgen gleich machen
Das Ziel besteht hier darin, zu bestimmen, ob bei einer beliebigen Anzahl von Operationen auf einem String-Array Str der Größe n alle Strings identisch gemacht werden können. Jedes Element kann aus einer Zeichenfolge entnommen und an einer beliebigen Stelle in derselben oder einer anderen Zeichenfolge wieder eingefügt werden, alles in einer Aktion. Gibt „Ja“ zurück, wenn die Zeichenfolgen gleich gemacht werden können, andernfalls „Nein“, was die Mindestanzahl der erforderlichen Operationen angibt.
Implementieren Sie ein Programm, um die Anzahl der Neuanordnungen von Zeichen zu minimieren, sodass alle gegebenen Zeichenfolgen gleich sind
Let us take the Input: n = 3, The input array, Str = {mmm, nnn, ooo}
The output obtained : Yes 6
Die drei im Array Str bereitgestellten Strings können mit mindestens 6 Operationen in den gleichen String mno umgewandelt werden.
{mmm, nnn, ooo} −> {mm, mnnn, ooo} {mm, mnnn, ooo} −> {m, mnnn, mooo} {m, mnnn, mooo} −> {mn, mnn, mooo} {mn, mnn, mooo} −> {mn, mn, mnooo} {mn, mn, mnooo} −> {mno, mn, mnoo} {mno, mn, mnooo} −> {mno, mno, mno}
Let us take the Input: n = 3, The input array, Str = {abc, aab, bbd}
The output obtained: No
Mit dem bereitgestellten String-Array Str kann nicht derselbe String generiert werden.
Let us take the Input: n = 3, The input array, Str = {xxy, zzz, xyy}
The output obtained : Yes 4
Alle drei Strings des bereitgestellten Arrays Str können mit mindestens 4 Operationen in denselben String xyz umgewandelt werden.
Um die Anzahl der Größenänderungen von Zeichen zu minimieren, um alle gegebenen Zeichenfolgen gleich zu machen, verwenden wir die folgende Methode.
Die Lösung für dieses Problem besteht darin, die Anzahl der Zeichenneupositionierungen zu minimieren, sodass alle gegebenen Zeichenfolgen gleich sind
Das Ziel, alle Zeichenfolgen gleich zu machen, kann erreicht werden, wenn die Buchstaben in allen Zeichenfolgen gleichmäßig verteilt sind. Das heißt, die Häufigkeit jedes Zeichens im Array muss durch eine Zahl der Größe „n“ teilbar sein.
Der minimale Algorithmus zur Neupositionierung von Zeichen, der erforderlich ist, um alle gegebenen Zeichenfolgen gleich zu machen, ist wie folgt
Schritt 1 − Starten
Schritt 2 – Definieren Sie eine Funktion, um zu prüfen, ob die Zeichenfolgen identisch werden können
Schritt 3 – Definieren Sie ein Array, um die Häufigkeiten aller Zeichen zu speichern. Hier definieren wir „fre“.
Schritt 4 - Durchlaufen Sie das bereitgestellte String-Array.
Schritt 5 – Durchlaufen Sie jedes Zeichen der angegebenen Zeichenfolge Str.
Schritt 6 – Aktualisieren Sie die erhaltene Häufigkeit
Schritt 7 – Überprüfen Sie nun die Zeichen jedes Buchstabens
Schritt 8 – Wenn die Häufigkeit nicht durch eine Zahl der Größe n teilbar ist, geben Sie „Nein“ ein
Schritt 9 – Teilen Sie die Häufigkeit jedes Zeichens durch die Größe n
Schritt 10 – Definieren Sie eine Ganzzahlvariable „Ergebnis“ und speichern Sie das Ergebnis als Mindestanzahl von Operationen
Schritt 11 – Speichern Sie die Häufigkeit jedes Zeichens in der Originalzeichenfolge „org“
Schritt 12 – Ermitteln Sie auch die Anzahl der zusätzlichen Zeichen
Schritt 13 – Drucken Sie „Ja“ und das erhaltene Ergebnis aus.
Schritt 14 − Stopp
Dies ist eine C-Programmimplementierung des oben genannten Algorithmus, um die Anzahl der Neupositionierungszeichen zu minimieren, sodass alle gegebenen Zeichenfolgen gleich sind.
#include <stdio.h> #include <string.h> #include <stdlib.h> // Define a function to check if the strings could be made identical or not void equalOrNot(char* Str[], int n){ // Array fre to store the frequencies of all the characters int fre[26] = {0}; // Traverse the provided array of strings for (int i = 0; i < n; i++) { // Traverse each characters of the given string Str for (int j = 0; j < strlen(Str[i]); j++){ // Update the frequencies obtained fre[Str[i][j] - 'a']++; } } // now check for every character of the alphabet for (int i = 0; i < 26; i++){ // If the frequency is not divisible by the size n, then print No. if (fre[i] % n != 0){ printf("No\n"); return; } } // Dividing the frequency of each of the character with the size n for (int i = 0; i < 26; i++) fre[i] /= n; // Store the result obtained as the minimum number of operations int result = 0; for (int i = 0; i < n; i++) { // Store the frequency of each od the characters in the original string org int org[26] = {0}; for (int j = 0; j < strlen(Str[i]); j++) org[Str[i][j] - 'a']++; // Get the number of additional characters as well for (int i = 0; i < 26; i++){ if (fre[i] > 0 && org[i] > 0){ result += abs(fre[i] - org[i]); } } } printf("Yes %d\n", result); return; } int main(){ int n = 3; char* Str[] = { "mmm", "nnn", "ooo" }; equalOrNot(Str, n); return 0; }
Yes 6
Ähnlich können wir die Anzahl der Zeichenneupositionierungen minimieren, um alle gegebenen Zeichenfolgen gleich zu machen.
In diesem Artikel wird die Herausforderung angesprochen, ein Programm zu erhalten, das die Anzahl der Zeichenneupositionierungen minimiert, um alle gegebenen Zeichenfolgen gleich zu machen.
C-Programmiercode und Algorithmen werden bereitgestellt, um die Anzahl der Neuanordnungen von Zeichen zu minimieren, sodass alle gegebenen Zeichenfolgen gleich sind.
Das obige ist der detaillierte Inhalt vonMinimieren Sie die Anzahl der Neuanordnungen von Zeichen, die alle gegebenen Zeichenfolgen gleich machen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!