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.

Problemstellung

Implementieren Sie ein Programm, um die Anzahl der Neuanordnungen von Zeichen zu minimieren, sodass alle gegebenen Zeichenfolgen gleich sind

Beispiel Beispiel 1

Let us take the Input: n = 3, 
The input array, Str = {mmm, nnn, ooo}

The output obtained : Yes 6

Erklärung

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}

Beispielbeispiel 2

Let us take the Input: n = 3, 
The input array, Str = {abc, aab, bbd}

The output obtained: No

Erklärung

Mit dem bereitgestellten String-Array Str kann nicht derselbe String generiert werden.

Beispiel Beispiel 3

Let us take the Input: n = 3, 
The input array, Str = {xxy, zzz, xyy}

The output obtained : Yes 4

Erklärung

Alle drei Strings des bereitgestellten Arrays Str können mit mindestens 4 Operationen in denselben String xyz umgewandelt werden.

Lösungsmethode

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.

Algorithmus

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

Beispiel: C-Programm

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;
}

Ausgabe

Yes 6

Fazit

Ä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!