Trong bài toán này, chúng ta được cung cấp một chuỗi đầu vào gồm các ký tự viết thường. Nhiệm vụ của chúng ta là đ m ký tự xuất hiện gần đúng trong một chuỗi đầu vào .
Trong trường hợp có nhiều giá trị có cùng tần suất xuất hiện, chúng tôi cần in các giá trị nhỏ hơn về mặt từ vựng.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
string = “programming”
Đầu ra
g
Phương pháp tiếp cận giải pháp
Để tìm giải pháp cho vấn đề, chúng ta cần sắp xếp chuỗi đã đọc và sau đó duyệt qua chuỗi để chúng ta có thể tìm thấy ký tự có số lần xuất hiện tối đa trong chuỗi. Chúng tôi sẽ sử dụng phương pháp băm (phương pháp bảng băm) để khắc phục vấn đề này. Chuyển và băm từng ký tự riêng lẻ thành một mảng ký tự được gọi là băm.
Thông thường, kích thước mảng băm được phân bổ là 256. Nhưng nếu chuỗi chỉ chứa các ký tự từ 0 đến 127, chúng tôi có thể sử dụng bảng băm có kích thước 128, để chúng tôi có thể phân bổ kích thước bảng băm theo chuỗi.
Thuật toán
-
Đọc một chuỗi đầu vào.
-
Tạo một hàm để tính toán ký tự xuất hiện lớn nhất trong chuỗi.
-
Tạo một mảng để giữ số lượng các ký tự riêng lẻ và khởi tạo mảng bằng 0.
-
Tạo mảng đếm ký tự từ chuỗi đầu vào.
-
Khởi tạo số lượng và kết quả tối đa.
-
Duyệt qua chuỗi và duy trì số lượng của nhau.
-
Cuối cùng, hãy tìm ký tự có số lượng lớn nhất và in nó.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#include <bits/stdc++.h>
using namespace std;
char findMaxOccuringChar(char str[]){
int freq[26] = { 0 };
int maxFreq = -1;
char maxFreqChar;
int len = strlen(str);
for (int i = 0; i < len; i++)
freq[str[i] - 'a']++;
for (int i = 0; i < 26; i++)
if (maxFreq < freq[i]) {
maxFreq = freq[i];
maxFreqChar = (char)(i + 'a');
}
return maxFreqChar;
}
int main(){
char str[] = "programming";
cout<<"Maximum occurring character of input string is "<<findMaxOccuringChar(str);
return 0;
} Đầu ra
Maximum occurring character of input string is g