数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用数字 M 构造 N 的最大计数，其中 2 和 5 相同，6 和 9 相同
最大计数是指可能的最大计数。这里我们给定一个整数 N 和一个整数字符串 M。我们的任务是返回使用整数字符串 M 的数字构造数字 N 的最大计数。同时，我们可以将 2 和 5 视为相同，将 6 和 9 视为相同。
示例
输入 1
N = 29 M = "2569783" Output 1: 2
说明 − 由于 5 等于 2，6 等于 9，因此我们共有两个“2”和两个“9”。因此，使用字符串 M (2596783) 的数字构造数字 N (29) 的最大计数为 2。
输入 2
N = 999 M = 6666925 Output 2: 1
方法
让我们逐步讨论这种方法：
首先，我们将创建一个函数“maxCountOfN”，该函数将给定的字符串“M”和数字“N”作为参数，并将所需的整数“maxCount”作为返回值。
在函数中，我们将创建一个哈希映射“mp”来存储字符串“M”中每个数字的频率。
我们定义一个变量“len”来存储字符串“M”的大小。
遍历字符串“M”，从索引“i = 0”到小于等于“len”，并在循环中执行以下操作：
如果我们得到一个数字“2”，我们将它转换为“5”。
如果我们得到一个数字“6”，我们将它转换为“9”。
在“mp”映射中计算每个数字的频率，作为字符-整数对。
创建另一个哈希映射“mpN”来存储数字 N 的数字频率。
使用 while 循环遍历数字“N”，直到 N 大于 0，并在循环中执行以下操作：
创建一个整数“rem”来存储数字的最后一位。
检查 rem 是否为 2，如果是，则将其转换为 5。
检查 rem 是否为 6，如果是，则将其转换为 9。
在“mpN”映射中计算每个数字的频率，作为字符-整数对。即，将整数作为字符存储在映射中，如“mpN[rem + ‘0’]”。
将 N 减少到 N%10 以去除数字的最后一位。
我们创建一个变量“maxCount”，其中我们存储“INT_MAX”。
最后，我们遍历映射“mpN”来查找 N 的最大计数，并在循环中执行以下操作：
创建一个变量“key”，其中我们存储数字的数字。
检查 key 是否存在于字符串的映射中，如果不存在，则意味着我们无法使用字符串“M”的数字创建数字“N”，我们返回“0”。
创建一个变量“tempCount”，其中我们存储值（将字符串 M 中数字的频率除以 N 的当前数字的频率）。
在 maxCount 中，我们存储 tempCount 和 maxCount 的最小值，因为只有当数字“N”的每个数字都存在于字符串“M”中时，才有可能构造数字“N”。
返回 maxCount
示例
#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;
}
输出
The max count of making the number 29 using the digits of the string 2569783 is 2
结论
在本教程中，我们实现了一个程序，用于查找使用数字 M 构造 N 的最大计数，其中 2 和 5 相同，6 和 9 相同。我们实现了一种哈希方法，因为我们必须存储频率，时间复杂度为 O(N+M)，空间复杂度为 O(N+M)。其中 M 是字符串的大小，N 是数字的大小。
浏览量 128 次
