Übersetzen Sie für Q-Abfragen Folgendes ins Chinesische: In einer ternären Zeichenfolge die Mindestanzahl an Zeichen, die ersetzt werden müssen, um alle palindromischen Teilzeichenfolgen zu entfernen

Ein Palindrom-String ist ein String, der seinem umgekehrten String entspricht. Bei einer gegebenen Zeichenfolge mit „0“, „1“ und „2“ und einem Array Q der Länge N stellt jeder Index des angegebenen Arrays einen Bereich dar, und der Bereich wird durch ein Wertepaar der Form dargestellt. Wir müssen die Mindestanzahl an Zeichen ermitteln, die in einem bestimmten Bereich ersetzt werden müssen, um sicherzustellen, dass der Bereich keine palindromischen Teilzeichenfolgen enthält.

Beispiel Beispiel

Input1: string s: “01001020002”, int Q = {{0,4}, {2,5}, {5,10}};

Output: 1 1 3

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

Für den Bereich 0 bis 4 haben wir zwei Palindrome 010 und 1001, wir können den Index 2 in „2“ ändern, sodass keine Palindrome mehr vorhanden sind.

Für den Bereich 2 bis 5 haben wir nur eine Palindromzahl, nämlich 010, die geändert werden kann, indem die erste Null in 2 geändert wird.

Für Zahlen im Bereich von 5 bis 10 haben wir die Palindromzahlen 020, 000 und 20002. Wir können die erste 2 in „1“, die „0“ des nächsten Index in „2“ und den Wert des vorletzten Index in „1“ ändern, um alle Palindrome zu entfernen.

Die chinesische Übersetzung von „Naiver Ansatz“ lautet: „Naiver Ansatz“.

Bei dieser Methode besteht die Idee darin, alle Kombinationen eines bestimmten Bereichs zu erhalten und die Mindestanzahl an Änderungen zu ermitteln, die für eine Kombination ohne Palindrome erforderlich sind. Das Problem ist jedoch die zeitliche Komplexität.

Um diese Methode zu implementieren, müssen wir einen rekursiven Aufruf durchführen und die Zeichenfolge durchlaufen. Bei jedem Index haben wir drei Möglichkeiten, wodurch die Zeitkomplexität zum Abrufen aller Zeichenfolgen 3^N beträgt. Jetzt müssen wir Q-Anfragen beantworten und für jeden Fall prüfen, ob das Entfernen der Palindromzeichenfolge die Zeitkomplexität zu O(Q*N*(3^N)) macht.

Für rekursive Aufrufe müssen wir den Raum N beibehalten, was bedeutet, dass die Raumkomplexität O(N) ist.

Dynamische Planung

Die chinesische Übersetzung von

Idee

lautet:

Idee

Die Idee dieser Frage ist, dass wir keine Palindromzahl im angegebenen Bereich finden müssen. Die minimal mögliche Palindromlänge beträgt 2 für gerade Zahlen und 3 für ungerade Zahlen.

Wir haben drei verschiedene Charaktere und wir brauchen sie alle, um die gegebene Zeichenfolge ohne Palindrome zu erstellen. Es gibt Gesamtgrößenauswahlmöglichkeiten oder Sequenzen. Wir können die Sequenzen so bilden, dass keine Palindrome existieren und diese Sequenzen Permutationen der Zeichenfolge „012“ sind.

Wir werden ein dp-Array oder einen dp-Vektor verwenden, um alle möglichen Fälle zu speichern. Jede Sequenz ergibt eine geringere Anzahl von Zeichen und wir werden diese Sequenz verwenden.

Umsetzung

Im Implementierungsteil erstellen wir zunächst eine Funktion, die eine Zeichenfolge, eine Sequenz, einen DP-Vektor und eine Anzahl von Sequenzen als Parameter akzeptiert und den DP-Vektor aktualisiert.

In dieser Funktion aktualisieren wir zunächst den Wert des ersten Index und dann für jeden nicht übereinstimmenden Fall den Wert des aktuellen Index des DP-Vektors.

Wir werden eine weitere Funktion erstellen, in der wir alle möglichen Sequenzen manuell eingeben, sie in einem Array speichern und einen DP-Vektor erstellen.

Wir rufen die obige Funktion auf, indem wir den Wert zur Vorverarbeitung übergeben, und beantworten dann jede Abfrage, indem wir sie einzeln durchgehen.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

#include <bits/stdc++.h>
#define SIZE 100005
using namespace std;
// function to get the pre-processing of the results 
void preprocess(string& str, string& seq, vector<vector<int>>&dp, int n, int i){
   dp[i][0] = (str[0] != seq[0]); // initialzie dp vector 
   for (int j = 1; j < n; j++) {
   
      // storing the results if matched then adding zero otherwise one
      dp[i][j] = dp[i][j - 1] + (str[j] != seq[j % 3]);
   }
   return;
}

// function to find the number of changes required for each query 
void changesReq(string str, vector<pair<int, int>> Q){
   int len = str.length(); // size of the given string 
   int q = Q.size(); // number of queries 
   vector<vector<int>>dp(6,vector<int>(len)); // dp vector to store the states results 
   
   // vector to store each possible non-palindromic sequency 
   vector<string> seq= { "012", "021", "102", "120", "201", "210" };
   for (int i = 0; i < 6; i++){
   
      // for each sequence storing state results in vector 
      preprocess(str, seq[i], dp, len, i);
   }	
   
   // getting all the queries 
   for (int i = 0; i < q; i++){
      int l = Q[i].first;
      int	r = Q[i].second;
      int ans = INT_MAX;
      
      // finding the minimum cost amount 
      for (int j = 0; j < 6; j++) {
         // Find the cost
         ans = min(ans, dp[j][r] - dp[j][l] + (str[l] != seq[j][l%3]));
      }
      cout <<ans<<"  ";
   }
}
int main(){
   string str = "01001020002";
   vector<pair<int, int>>Q = {{0,4}, {2,5}, {5,10}};
   
   // calling the function 
   cout<<"The minimum characters to be replaced in the Ternary string to remove all palindromic substrings for Q queries is "<<endl;
   changesReq(str, Q);
   return 0;
}

Ausgabe

The minimum characters to be replaced in the Ternary string to remove all palindromic substrings for Q queries is 
1  1  3  

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N + Q), wobei N die Anzahl der Zeichen in der Zeichenfolge und Q die Anzahl der Abfragen ist. Die räumliche Komplexität des obigen Codes beträgt O(N), da wir den Zustand in einem Vektor der Größe N speichern.

Fazit

In diesem Tutorial haben wir einen Code implementiert, um die Mindestanzahl an Zeichen herauszufinden, die bei einigen Abfragen in einem bestimmten Bereich geändert werden müssen, damit keine Palindrom-Zeichenfolge zurückbleibt. Wir haben diesen Code mithilfe des Konzepts der dynamischen Programmierung mit einer zeitlichen Komplexität von O(N+Q) und einer räumlichen Komplexität von O(N) implementiert.

Das obige ist der detaillierte Inhalt vonÜbersetzen Sie für Q-Abfragen Folgendes ins Chinesische: In einer ternären Zeichenfolge die Mindestanzahl an Zeichen, die ersetzt werden müssen, um alle palindromischen Teilzeichenfolgen zu entfernen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!