Finden Sie das Zeichen, das nach der Ausführung einer bestimmten Operation am häufigsten vorkommt

In diesem Artikel untersuchen wir das Konzept, die häufigsten Zeichen in einer Zeichenfolge zu finden, nachdem eine bestimmte Reihe von Operationen ausgeführt wurde. Diese Frage taucht häufig bei Programmierherausforderungen und Interviews auf, und wenn Sie die Lösung haben, können Sie Ihre String-Manipulations- und Algorithmenfähigkeiten stärken. Wir erklären die Problemstellung, diskutieren den verwendeten Algorithmus, zeigen die C++-Implementierung und stellen Testfallbeispiele zur Verfügung, um die Lösung zu demonstrieren.

Problemstellung

Finden Sie bei einer gegebenen Zeichenfolge s und einer Reihe von Operationen das größte Vorkommen des Zeichens, nachdem alle Operationen ausgeführt wurden. Jede Operation besteht aus einem Paar (i, j), was bedeutet, dass wir die Zeichen an den Positionen i und j in der Zeichenfolge austauschen möchten.

Algorithmus

• Erstellen Sie ein Häufigkeitsarray, um die Häufigkeit des Vorkommens jedes Zeichens in einer Zeichenfolge zu speichern.

• Iterative Operation, Austausch von Zeichen an bestimmten Positionen.

• Aktualisieren Sie das Frequenzarray nach jedem Austausch.

• Durchlaufen Sie das Frequenzarray, um das Zeichen zu finden, das am häufigsten vorkommt.

C++-Implementierung

Beispiel

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

char maxOccurringChar(const std::string &s, const std::vector<std::pair<int, int>> &operations) {
   std::vector<int> frequency(26, 0);
   std::string modifiedString = s;
   
   // Initialize the frequency array with the original string's character occurrences
   for (char c : modifiedString) {
      frequency[c - 'a']++;
   }
   
   for (const auto &op : operations) {
      int i = op.first;
      int j = op.second;
   
      // Decrement the frequency of the characters being swapped
      frequency[modifiedString[i] - 'a']--;
      frequency[modifiedString[j] - 'a']--;
   
      // Perform the swap
      std::swap(modifiedString[i], modifiedString[j]);
   
      // Increment the frequency of the swapped characters
      frequency[modifiedString[i] - 'a']++;
      frequency[modifiedString[j] - 'a']++;
   }

   // Find the character with the maximum occurrence
   int maxFrequency = 0;
   char maxChar = 'a';
   for (int i = 0; i < 26; i++) {
      if (frequency[i] > maxFrequency) {
         maxFrequency = frequency[i];
         maxChar = 'a' + i;
      }
   }
   
   return maxChar;
}

int main() {
   std::string s = "aabcbdb";
   std::vector<std::pair<int, int>> operations = { {1, 4}, {2, 5} };
   
   char maxChar = maxOccurringChar(s, operations);
   std::cout << "The maximum occurring character after performing the operations is: " << maxChar << std::endl;
   
   return 0;
}

Ausgabe

The maximum occurring character after performing the operations is: b

Testfallbeispiel

Betrachten wir das folgende Beispiel -

• String: „aabcbdb“

• Bedienung: { {1, 4}, {2, 5} }

• Führen Sie die erste Operation (1, 4) aus: „abacbdb“

• Führen Sie die zweite Operation (2, 5) aus: „abcabdb“

Nach der Ausführung des Vorgangs wird die Zeichenfolge zu „abcabdb“. Das häufigste Zeichen in der geänderten Zeichenfolge ist „b“, das dreimal vorkommt.

Fazit

In diesem Artikel untersuchen wir das Problem, die häufigsten Zeichen in einer Zeichenfolge zu finden, nachdem eine bestimmte Reihe von Operationen ausgeführt wurde. Wir diskutieren den Algorithmus, schlagen eine überarbeitete C++-Implementierung vor und stellen einen Beispieltestfall zur Verfügung, um die Lösung zu demonstrieren. Das Beherrschen solcher Fragen kann dazu beitragen, Ihre String-Manipulations- und Algorithmusfähigkeiten zu stärken, die für Programmierherausforderungen und Interviews von entscheidender Bedeutung sind. Denken Sie daran, das Frequenzarray bei Bedarf sorgfältig zu initialisieren und zu aktualisieren, um genaue Ergebnisse sicherzustellen.

Das obige ist der detaillierte Inhalt vonFinden Sie das Zeichen, das nach der Ausführung einer bestimmten Operation am häufigsten vorkommt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!