資料結構
網路
關係資料庫管理系統 (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 次
