Bei Verwendung der Zahlen M beträgt die maximale Anzahl N, wobei 2 und 5 sowie 6 und 9 als gleich betrachtet werden können

Max count ist eine mögliche maximale Anzahl. Hier erhalten wir eine ganze Zahl N und eine Zeichenfolge mit einer ganzen Zahl M. Unsere Aufgabe besteht darin, die Zahl N aus den Ziffern der ganzen Zahl M zu bilden und die maximale Anzahl zurückzugeben. Gleichzeitig können wir uns 2 und 5 als dieselbe Zahl und 6 und 9 als dieselbe Zahl vorstellen.

Beispielbeispiel

Geben Sie 1 ein

N = 29
M = "2569783"
Output 1: 2

Erklärung − Da 5 und 2 gleich sind und 6 und 9 gleich sind, haben wir zwei „2er“ und zwei „9er“. Daher beträgt die maximale Anzahl für die Verwendung der Ziffern der Zeichenfolge M (2596783) zur Bildung der Zahl N (29) 2.

Geben Sie 2 ein

N = 999
M = 6666925
Output 2: 1

Methode

Lassen Sie uns die folgende Methode Schritt für Schritt besprechen –

• Zuerst erstellen wir eine Funktion namens „maxCountOfN“, die die gegebene Zeichenfolge „M“ und die Zahl „N“ als Parameter übernimmt und die erforderliche Ganzzahl „maxCount“ als Rückgabewert zurückgibt.

• In dieser Funktion erstellen wir eine Hash-Map „mp“, um die Häufigkeit jeder Zahl in der Zeichenfolge „M“ zu speichern.

• Wir definieren eine Variable „len“, um die Größe der Zeichenfolge „M“ zu speichern.

• Durchlaufen Sie die Zeichenfolge „M“ ausgehend vom Index „i = 0“, bis sie kleiner oder gleich „len“ ist, und führen Sie die folgenden Operationen in dieser Schleife aus:

• Wenn die Zahl, die wir erhalten, „2“ ist, wandeln wir sie in „5“ um.

• Wenn wir eine Zahl als „6“ erhalten, wandeln wir sie in „9“ um.

• Zählen Sie die Häufigkeit jeder Zahl in der „mp“-Karte als Zeichen-Ganzzahl-Paar.

• Erstellen Sie eine weitere Hash-Map „mpN“, um die Häufigkeit der Zahl N zu speichern

• Verwenden Sie eine While-Schleife, um die Zahl „N“ zu durchlaufen, bis N größer als 0 ist, und führen Sie die folgenden Operationen in dieser Schleife aus -

• Erstellen Sie eine Ganzzahl „rem“, um das letzte Element der Zahl zu speichern

• Überprüfen Sie, ob es 2 ist, und konvertieren Sie es in 5

• Überprüfen Sie, ob rem 6 ist, und konvertieren Sie es in 9

• Zählen Sie die Häufigkeit jeder Zahl in der „mpN“-Karte als Zeichen-Ganzzahl-Paare. Das heißt, die Ganzzahl wird als Zeichen in der Karte gespeichert, beispielsweise „mpN[rem + ‚0‘]“.

• Reduzieren Sie N auf N%10, um die letzte Ziffer der Zahl zu entfernen

• Wir erstellen eine Variable „maxCount“, die „INT_MAX“ speichert.

• Abschließend durchlaufen wir die Karte „mpN“, um die maximale Anzahl von N zu ermitteln, und führen in dieser Schleife Folgendes aus:

• Speichern Sie die Anzahl der Ziffern in der Variablen „Schlüssel“

• Überprüfen Sie, ob der Schlüssel in der Zeichenfolgenzuordnung vorhanden ist. Wenn er nicht vorhanden ist, bedeutet dies, dass wir die Zahl „N“ nicht aus den Zahlen der Zeichenfolge „M“ erstellen können. Wir geben „0“ zurück.

• Erstellen Sie eine Variable in der Variablen „tempCount“, in der wir den Wert speichern (dividieren Sie die Häufigkeit der Zahlen in Zeichenfolge M durch die aktuelle Häufigkeit der Zahlen in N).

• In maxCount speichern wir den Mindestwert von tempCount und maxCount, da es nur möglich ist, die Zahl „N“ zu generieren, wenn jede Ziffer der Zahl „N“ in der Zeichenfolge „M“ vorkommt

• MaxCount zurückgeben

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

#include <bits/stdc++.h>
using namespace std;
int maxCountOfN(int N, string M){
   map< char, int >mp; //created hashmap to store the frequency of each digit of //string
   int len = M.size(); // getting the size of the string     
   // iterating string using for loop 
   for(int i=0;i<len;i++){
      if(M[i] == '2'){
         M[i] = '5'; // replace 2 with 5
      }
      else if(M[i] == '6'){ 
         M[i] = '9'; // replace 6 with 9
      }
      mp[M[i]]++; //count frequency of digit of string
   }    
   // creating another hashmap to store the frequency of digit of the number N
   map<char, int>mpN;      
   // iterating number 'N' using while loop     
   while(N > 0){
      int rem = N % 10; // Get the last digit as the remainder        
      //Replace 2 with 5
      if(rem == 2){
         rem = 5;
      }
      //Replace 6 with 9
      if(rem == 6){
         rem = 9;
      }        
      mpN[rem + '0']++; //count frequency of digit of number        
      N = N / 10;
   }    
   int maxCount = INT_MAX;
   //Trvaerse the hashmap of the number to get the maxCount
   for(auto el : mpN){
      // Get the key which is a digit from the number N to be formed
      int key = el.first; 
      // If the key is not present in the string M, then the number N cannot be formed
      if (!mp.count(key))
      return 0; 
      // Divide the frequency of the digit from the string M with the frequency of the current digit of N
      int tempCount = mp[key] / el.second; 
      // Choose the minimum
      maxCount = min(maxCount, tempCount);
   }    
   // returning the maximum count 
   return maxCount;
}
// main function 
int main(){    
   int N = 29; // given number
   string M = "2569783";// given string    
   // calling the function to get a maximum count of N 
   int maxCount = maxCountOfN(N, M);   
   cout<<"The max count of making the number "<< N << " using the digits of the string " << M << " is "<< maxCount<<endl;   
   return 0;
}

Ausgabe

The max count of making the number 29 using the digits of the string 2569783 is 2

Fazit

In diesem Tutorial haben wir ein Programm implementiert, um die maximale Anzahl von N mithilfe von Ziffern von M zu ermitteln, sodass 2 und 5 bzw. 6 und 9 als gleich behandelt werden können. Wir haben einen Hashing-Ansatz implementiert um die Häufigkeit mit der zeitlichen Komplexität von O(N+M) und der räumlichen Komplexität von O(N+M) zu speichern. Dabei ist M die Größe der Zeichenfolge und N die Größe der Zahl.

Das obige ist der detaillierte Inhalt vonBei Verwendung der Zahlen M beträgt die maximale Anzahl N, wobei 2 und 5 sowie 6 und 9 als gleich betrachtet werden können. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!