Die lexikografisch größte Zeichenfolge, deren Summe der Zeichen gleich N ist

Problemstellung

Wir erhalten eine positive ganze Zahl. Wir müssen eine Zeichenfolge finden, die aus Kleinbuchstaben besteht, sodass die Summe aller Zeichen in der Zeichenfolge gleich num ist und die Zeichenfolge in lexikografischer Reihenfolge die größte ist. Hier ist „a“ = 1, „b“ = 2, „c“ = 3, „d“ = 4, …, „z“ = 26.

Wir müssen das Zeichen „z“ am Anfang der Zeichenfolge verwenden, um die größte Wörterbuchzeichenfolge zu erstellen. Schließlich müssen wir das letzte Zeichen basierend auf dem Wert „num % 26“ verwenden.

Beispiel

Eintreten

num = 30

Ausgabe

‘zd’

Erklärung

Erklärung

‘zd‘ ist die größte lexikografische Zeichenfolge mit einer Zeichensumme von 30 (z = 26 + d = 4).

Eintreten

3

Ausgabe

‘c’

Erklärung

Erklärung

‘c‘ repräsentiert 3 selbst.

Eintreten

130

Ausgabe

‘zzzzz’

Erklärung

Erklärung

Die Summe der Werte jedes Zeichens „zzzzz“ beträgt 130.

Methode 1

Diese Methode verwendet eine While-Schleife, um eine resultierende Zeichenfolge zu erstellen. Wir iterieren, bis eine Zahl einen Wert größer oder gleich 26 hat. Bei jeder Iteration fügen wir „z“ zur Zeichenfolge hinzu und subtrahieren 26 von der Zahl. Abschließend fügen wir basierend auf dem Rest ein Zeichen zur Zeichenfolge hinzu.

Algorithmus

• Schritt 1 – Führen Sie die Funktion findString() aus, indem Sie einen numerischen Wert als Parameter übergeben.

• Schritt 2 – Initialisieren Sie die Ergebnisvariable vom Typ „String“ mit einer leeren Zeichenfolge, um die Ergebniszeichenfolge zu speichern.

• Schritt 3 – Verwenden Sie eine While-Schleife, um zu iterieren, bis der Wert von „num“ größer oder gleich 26 ist.

• Schritt 4 – Fügen Sie in der while-Schleife das Zeichen „z“ zur resultierenden Zeichenfolge hinzu.

• Schritt 5 – Subtrahiere 26 vom Wert einer Zahl.

• Schritt 6 – Wenn die While-Schleifeniteration abgeschlossen ist, prüfen Sie, ob der Wert von num größer als 0 ist. Wenn ja, hängen Sie das letzte Zeichen basierend auf dem Wert der Variablen „num“ an die Zeichenfolge an.

• Schritt 7 – Rückgabe der Ergebniszeichenfolge.

Beispiel

Beispiel

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

Ausgabe

The resultant string is zzzr

• Zeitkomplexität - O(num), da die while-Schleife num/26 Mal ausgeführt wird, was gleich O(num) ist.

• Raumkomplexität - O(num), da eine Zeichenfolge höchstens (num/26 + 1) Zeichen enthalten kann.

Methode 2

In dieser Methode erstellen wir mit dem String()-Konstruktor einen String der Länge N. Wir verwenden Modulo- und Divisionsoperatoren, um die Gesamtzahl der Zs in der Zeichenfolge zu ermitteln.

Algorithmus

• Schritt 1 – Definieren Sie die Variable „totalZ“ und initialisieren Sie sie mit num/26.

• Schritt 2 – Definieren Sie die Variable „rem“ und initialisieren Sie sie mit „num%26“.

• Schritt 3 – Verwenden Sie dies, um eine Zeichenfolge mit „totalZ“ und „z“-Zeichen zu erstellen, indem Sie „totalZ“ als erstes Argument und „z“ als zweites Argument an den string()-Konstruktor String übergeben. Hängen Sie es gleichzeitig an die Zeichenfolge „result“ an.

• Schritt 4 – Wenn der Wert von „rem“ nicht gleich 0 ist, hängen Sie das letzte Zeichen basierend auf dem Wert der Variablen „rem“ an die Zeichenfolge an.

  < /里>

• Schritt 5 – Geben Sie die Ergebniszeichenfolge zurück.

Beispiel

Beispiel

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

Ausgabe

The resultant string is zz

• Zeitkomplexität - O(num) Erstellen Sie als String-Konstruktor einen String mit totalz Zeichen.

• Raumkomplexität - O(num)

Fazit

Wir haben zwei Möglichkeiten kennengelernt, Zahlen in Zeichenfolgen umzuwandeln. Wir haben in der ersten Methode eine while-Schleife und in der zweiten Methode den string()-Konstruktor verwendet. Allerdings haben beide Methoden die gleiche räumliche und zeitliche Komplexität, die zweite Methode ist jedoch besser lesbar.

Das obige ist der detaillierte Inhalt vonDie lexikografisch größte Zeichenfolge, deren Summe der Zeichen gleich N ist. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!