La chaîne lexicographiquement la plus grande dont la somme des caractères est égale à N

Énoncé du problème

Nous recevons un nombre entier positif. Nous devons trouver une chaîne composée de lettres minuscules telle que la somme de tous les caractères de la chaîne soit égale à num et que la chaîne soit la plus grande dans l'ordre lexicographique. Ici, 'a' = 1, 'b' = 2, 'c' = 3, 'd' = 4,…., 'z' = 26.

Nous devons utiliser le caractère « z » au début de la chaîne pour créer la plus grande chaîne de dictionnaire. Enfin, nous devons utiliser le dernier caractère basé sur la valeur num % 26.

Exemple

Entrez

num = 30

Sortie

‘zd’

Explication

Explication

« zd » est la plus grande chaîne lexicographique avec une somme de caractères de 30 (z = 26 + d = 4).

Entrez

3

Sortie

‘c’

Explication

Explication

‘c’ représente 3 lui-même.

Entrez

130

Sortie

‘zzzzz’

Explication

Explication

La somme des valeurs de chaque caractère « zzzzz » est de 130.

Méthode 1

Cette méthode utilisera une boucle while pour créer une chaîne résultante. Nous allons itérer jusqu'à ce qu'un nombre ait une valeur supérieure ou égale à 26, à chaque itération nous ajouterons « z » à la chaîne et soustrairons 26 du nombre. Enfin, nous ajouterons un caractère à la chaîne en fonction du reste.

Algorithme

• Étape 1 - Exécutez la fonction findString() en passant une valeur numérique comme paramètre.

• Étape 2 - Initialisez la variable résultat de type chaîne avec une chaîne vide pour stocker la chaîne résultat.

• Étape 3 - Utilisez une boucle while pour itérer jusqu'à ce que la valeur de 'num' soit supérieure ou égale à 26.

• Étape 4 - Dans la boucle while, ajoutez le caractère « z » à la chaîne résultante.

• Étape 5 - Soustrayez 26 de la valeur d'un nombre.

• Étape 6 - Lorsque l'itération de la boucle while est terminée, vérifiez si la valeur de num est supérieure à 0. Si tel est le cas, ajoutez le dernier caractère à la chaîne en fonction de la valeur de la variable « num ».

• Étape 7 - Renvoie la chaîne de résultat.

Exemple

Exemple

#include <bits/stdc++.h>
using namespace std;

// function to find the resultant string
string findString(int num) {
   // variable to store the resultant string
   string result = "";
   // using a while loop to find the resultant string
   while (num >= 26) {
      // append z to the resultant string
      result += 'z';
      // Decrease the number by 26
      num -= 26;
   }
   // Convert the remaining number to char and append to the resultant string
   if(num != 0) {
      result += char(num + 'a' - 1);
   }
   return result;
}

int main() {
   int num = 96;
   cout << "The resultant string is " << findString(num);
   return 0;
}

Sortie

The resultant string is zzzr

• Complexité temporelle - O(num), car la boucle while exécute num/26 fois, ce qui est égal à O(num).

• Complexité spatiale - O(num), car une chaîne peut contenir au plus (num/26 + 1) caractères.

Méthode 2

Dans cette méthode, nous allons créer une chaîne de longueur N à l'aide du constructeur String(). Nous utiliserons les opérateurs modulo et division pour obtenir le nombre total de z dans la chaîne.

Algorithme

• Étape 1 - Définissez la variable "totalZ" et initialisez-la avec num/26.

• Étape 2 - Définissez la variable 'rem' et initialisez-la avec 'num%26'.

• Étape 3 - Utilisez-le pour créer une chaîne contenant les caractères « totalZ » « z » en passant « totalZ » comme premier argument et « z » comme deuxième argument au constructeur string() String. En même temps, ajoutez-le à la chaîne « résultat ».

• Étape 4 - Si la valeur de 'rem' n'est pas égale à 0, ajoutez le dernier caractère à la chaîne en fonction de la valeur de la variable 'rem'.

  < /里>

• Étape 5 - Renvoie la chaîne « résultat ».

Exemple

Exemple

#include <bits/stdc++.h>
using namespace std;
// function to find the resultant string
string findString(int num) {
   // variable to store the resultant string
   string result = "";
   // variable to store the number of z's
   int totalZ = num / 26;
   // variable to store the remainder
   int rem = num % 26;
   // Using the string constructor to create a string with total number of totalZ 'z'.
   result += string(totalZ, 'z');
   // If the remainder is non-zero, then add the corresponding character
   if(rem != 0) {
      result += char(rem + 'a' - 1);
   }
   return result;
}
int main(){
   int num = 52;
   cout << "The resultant string is " << findString(num);
   return 0;
}

Sortie

The resultant string is zz

• Complexité temporelle - O(num) En tant que constructeur de chaîne, créez une chaîne contenant des caractères totalz.

• Complexité spatiale - O(num)

Conclusion

Nous avons appris deux façons de convertir des nombres en chaînes. Nous avons utilisé la boucle while dans la première méthode et le constructeur string() dans la deuxième méthode. Cependant, les deux méthodes ont la même complexité spatiale et temporelle, mais la seconde méthode est plus lisible.

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!