Code écrit en C++ : recherchez la chaîne lexicographiquement la plus petite composée des K premières lettres de l'alphabet, et les caractères adjacents ne peuvent pas être identiques

Dans le monde de la programmation, résoudre des problèmes de manipulation de chaînes est un défi courant et intéressant. Un problème clé est de savoir comment obtenir une chaîne lexicographiquement minimale en utilisant uniquement les K lettres de l'alphabet, tout en respectant des contraintes supplémentaires telles que la non-correspondance des caractères adjacents. Dans cet article, nous visons à approfondir ce problème et à proposer une solution efficace utilisant le langage de programmation C++. En détaillant les différentes méthodes utilisées dans la grammaire et en fournissant des détails algorithmiques étape par étape, nous pouvons introduire des techniques innovantes visant à obtenir de bons résultats dans différents domaines. Nous fournissons des instructions complètes sur le code exécutable pour chaque méthode afin de la rendre pratique pour les utilisateurs.

Grammaire

Avant d'explorer les algorithmes et les techniques, il est nécessaire d'établir la syntaxe utilisée dans les extraits de code qui suivent.

std::string findLexSmallestString(int n, int k);

Dans cette syntaxe, n fait référence au nombre de lettres de l'alphabet, k fait référence au nombre de lettres utilisées et la fonction génère la chaîne ordonnée lexicographiquement la plus basse qui satisfait aux conditions spécifiées.

Algorithme

Pour relever et résoudre le défi consistant à trouver la chaîne lexicographiquement minimale sans répétition entre caractères adjacents en utilisant uniquement jusqu'à K lettres de l'alphabet, nous avons formulé une approche méthodique sous la forme d'un algorithme.

• Initialisez une chaîne vide "ans" et un tableau/vecteur "used" pour suivre les caractères utilisés.

• Commencez à itérer à partir du premier caractère de l'alphabet.

• Ajoutez le caractère actuel à « ans » et marquez-le comme utilisé.

• Si "ans" a plusieurs caractères et que les deux derniers caractères sont identiques, recherchez le prochain caractère disponible en itérant du caractère actuel jusqu'à "n".

• Si aucun caractère disponible n'est trouvé, revenez en arrière en supprimant le dernier caractère de "ans" et en le marquant comme inutilisé.

• Répétez les étapes 3 à 5 jusqu'à ce que « ans » atteigne la longueur « k ».

• Renvoyez "ans" comme la plus petite chaîne lexicographique dans laquelle il n'y a pas deux caractères adjacents identiques, en utilisant toutes les premières K lettres de l'alphabet.

Méthode 1 : algorithme gourmand

Dans cette méthode, nous utiliserons une stratégie gloutonne pour construire la chaîne lexicographiquement la plus petite. Le même processus met l'accent sur un examen attentif de chaque caractère dans l'ordre tout en garantissant que les choix effectués tout au long du processus visent à minimiser la valeur lexicographique du résultat global.

Exemple

#include <iostream>
#include <vector>

std::string findLexSmallestGreedy(int n, int k) {
   std::string ans = "";
   std::vector<bool> used(n, false);

   for (int i = 0; i < n; i++) {
      for (int j = 0; j < k; j++) {
         if (!used[j]) {
            if (ans.empty() || ans.back() != 'a' + j) {
               ans += 'a' + j;
               used[j] = true;
               break;
            }
         }
      }
   }

   return ans;
}

int main() {
   int n = 5; // Assuming there are 5 letters in the alphabet
   int k = 3; // Assuming 3 letters will be used

   std::string result = findLexSmallestGreedy(n, k);
   std::cout << "Lexicographically Smallest String: " << result << std::endl;

   return 0;
}

Sortie

Lexicographically Smallest String: abc

Méthode 2 : Algorithme de retour en arrière

Cette stratégie consiste à utiliser le retour en arrière pour rechercher de manière exhaustive chaque combinaison de caractères tout en garantissant que les caractères consécutifs ne sont pas répétés. Par conséquent, en considérant chaque caractère à chaque position, nous pouvons trouver la chaîne lexicographiquement la plus petite qui satisfait les contraintes données.

Exemple

#include <iostream>
#include <vector>

bool findLexSmallestBacktracking(int n, int k, std::vector<char>& ans, std::vector<bool>& used) {
   if (ans.size() == k) {
      return true;
   }

   for (int i = 0; i < n; i++) {
      if (!used[i]) {
         if (ans.empty() || ans.back() != 'a' + i) {
            ans.push_back('a' + i);
            used[i] = true;

            if (findLexSmallestBacktracking(n, k, ans, used)) {
               return true;
            }

            ans.pop_back();
            used[i] = false;
         }
      }
   }

   return false;
}

std::string findLexSmallestStringBacktracking(int n, int k) {
   std::vector<char> ans;
   std::vector<bool> used(n, false);

   if (findLexSmallestBacktracking(n, k, ans, used)) {
      return std::string(ans.begin(), ans.end());
   }

   return "";
}

int main() {
   int n = 22;  // Assuming n = 22
   int k = 4;  // Assuming k = 4

   std::string result = findLexSmallestStringBacktracking(n, k);
   std::cout << "Lexicographically Smallest String: " << result << std::endl;

   return 0;
}

Sortie

Lexicographically Smallest String: abcd

Conclusion

Dans cet article, nous explorons le problème de trouver la chaîne lexicographiquement la plus petite en utilisant les K premières lettres de l'alphabet, avec la contrainte que deux caractères adjacents ne peuvent pas être identiques. Nous discutons de la syntaxe et proposons deux approches différentes pour résoudre ce problème : l'algorithme glouton et l'algorithme de retour en arrière. Les algorithmes gourmands emploient la stratégie consistant à minimiser la valeur lexicographique de la chaîne résultante, tandis que les algorithmes de backtracking explorent toutes les combinaisons possibles pour trouver la chaîne souhaitée. Les exemples de code C++ fournis démontrent l'implémentation de chaque méthode et nous permettent de générer efficacement des chaînes lexicographiquement minimales. Fort de ces connaissances, vous pouvez désormais résoudre en toute confiance des problèmes similaires de manipulation de chaînes et optimiser votre code en conséquence.

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!