Pour les requêtes Q, traduisez ce qui suit en chinois : Dans une chaîne ternaire, le nombre minimum de caractères qui doivent être remplacés pour supprimer toutes les sous-chaînes palindromiques.

Une chaîne palindrome est une chaîne qui est égale à sa chaîne inversée. Étant donné une chaîne contenant « 0 », « 1 » et « 2 », et un tableau Q de longueur N, chaque index du tableau donné représente une plage, et la plage est représentée par une paire de valeurs de la forme. Nous devons trouver le nombre minimum de caractères qui doivent être remplacés dans une plage donnée pour garantir qu'il n'y a pas de sous-chaînes palindromiques dans la plage.

Exemple Exemple

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

Output: 1 1 3

La traduction chinoise de

Explication

est :

Explication

Pour la plage 0 à 4, nous avons deux palindromes 010 et 1001, nous pouvons changer l'index 2 en '2' pour qu'il n'y ait plus de palindromes.

Pour la plage 2 à 5, nous n'avons qu'un seul numéro palindrome qui est 010, qui peut être modifié en changeant le premier zéro en 2.

Pour les nombres compris entre 5 et 10, nous avons les nombres palindromes 020, 000 et 20002. Nous pouvons changer les 2 premiers en « 1 », le « 0 » de l'index suivant en « 2 » et l'avant-dernier valeur de l'index en « 1 » pour supprimer tous les palindromes.

La traduction chinoise de

Approche Naive

est :

Approche Naive

Dans cette méthode, l'idée est d'obtenir toutes les combinaisons d'une plage donnée et de trouver le nombre minimum de changements requis pour une combinaison sans palindromes. Mais le problème est la complexité temporelle.

Pour implémenter cette méthode, nous devons effectuer un appel récursif et parcourir la chaîne. À chaque index, nous avons trois choix, ce qui rend la complexité temporelle d'obtention de toutes les chaînes 3^N. Maintenant, nous devons répondre aux requêtes Q, et pour chaque cas, nous devons vérifier si la suppression de la chaîne palindrome rend la complexité temporelle O(Q*N*(3^N)).

Pour les appels récursifs, nous devons maintenir l'espace de N, ce qui signifie que la complexité spatiale est O(N).

Planification dynamique

La traduction chinoise de

Idée

est :

Idée

L'idée de​​cette question est que nous n'avons pas besoin de trouver de nombre palindrome dans la plage donnée. La longueur minimale possible du palindrome est de 2 pour les nombres pairs et de 3 pour les nombres impairs.

Nous avons trois caractères différents et nous avons besoin de tous pour créer la chaîne donnée sans palindromes. Il existe des choix ou des séquences de taille totale, nous pouvons former les séquences de telle manière qu'aucun palindrome n'existe et ces séquences sont des permutations de la chaîne '012'.

Nous utiliserons un tableau dp ou un vecteur pour stocker tous les cas possibles, chaque séquence donnera moins de caractères et nous utiliserons cette séquence.

Mise en œuvre

Dans la partie implémentation, nous allons d'abord créer une fonction qui acceptera une chaîne, une séquence, un vecteur DP et un nombre de séquences comme paramètres et mettra à jour le vecteur DP.

Dans cette fonction, nous mettrons d'abord à jour la valeur du premier indice, puis pour chaque cas sans correspondance, nous mettrons à jour la valeur de l'indice actuel du vecteur DP.

Nous allons créer une autre fonction dans laquelle nous saisirons manuellement toutes les séquences possibles, les stockerons dans un tableau et créerons un vecteur DP.

Nous appellerons la fonction ci-dessus en passant une valeur pour le prétraitement, puis répondrons à chaque requête en la parcourant une par une.

La traduction chinoise de

Exemple

est :

Exemple

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

Sortie

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

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N + Q), où N est le nombre de caractères dans la chaîne et Q est le nombre de requêtes.

La complexité spatiale du code ci-dessus est O(N) car nous stockons l'état dans un vecteur de taille N.

Conclusion

Dans ce tutoriel, nous avons implémenté un morceau de code pour connaître le nombre minimum de caractères qui doivent être modifiés lors de certaines requêtes dans une plage donnée afin de ne pas laisser de chaîne palindrome. Nous avons implémenté ce code en utilisant le concept de programmation dynamique avec une complexité temporelle de O(N+Q) et une complexité spatiale de O(N).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!