Trong bài toán này, chúng ta được cung cấp một chuỗi. Và mỗi truy vấn Q có hai số nguyên l và r và ký tự ch. nhiệm vụ của chúng ta là tạo một chương trình để giải quyết các truy vấn về tần số của các ký tự trong chuỗi con trong C ++.
Mô tả sự cố :Ở đây với mỗi querry, chúng ta sẽ tìm tần suất xuất hiện của ký tự ‘ch’ trong chuỗi con str [l ... r].
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
str = “tutorialspoint” Q = 2 0 6 t 5 13 i
Đầu ra
2 2
Giải thích
Đối với truy vấn 1 - chuỗi con là "hướng dẫn", ký tự t xuất hiện 2 lần.
Đối với truy vấn 2 - chuỗi con là “ialspoint”, ký tự tôi xuất hiện 2 lần
Cách tiếp cận giải pháp
Cách tiếp cận đơn giản và dễ hiểu để giải quyết vấn đề là duyệt qua chuỗi he từ l đến r cho mỗi quả mọng và đếm sự xuất hiện của haracter ch trong chuỗi.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <bits/stdc++.h>
using namespace std;
struct Query{
int l, r;
char ch;
};
int CalcCharFreq(string str, Query queries){
int count = 0;
for(int i = queries.l; i < queries.r; i++){
if(str[i] == queries.ch )
count++;
}
return count;
}
int main(){
string str = "tutorialspoint";
int Q = 2;
Query queries[Q];
queries[0].l = 0;
queries[0].r = 5;
queries[0].ch = 't';
queries[1].l = 5;
queries[1].r = 13;
queries[1].ch = 'i';
for(int i = 0; i<Q; i++)
cout<<"For Query "<<(i+1)<<": The frequency of occurrence of character '"<<queries[i].ch<<"' is "<<CalcCharFreq(str, queries[i])<<"\n";
return 0;
} Đầu ra
For Query 1: The frequency of occurrence of character 't' is 2 For Query 2: The frequency of occurrence of character 'i' is 2
Một cách tiếp cận khác để giải quyết vấn đề bằng cách sử dụng một mảng được tính toán trước. Ở đây, chúng tôi sẽ tạo một mảng 2D sẽ lưu trữ tần suất của các ký tự cho đến chỉ mục cụ thể, tức là freq [3] [2] sẽ lưu trữ tần suất của ký tự 'c' ở chỉ mục 2. Ban đầu, tất cả các tần số đều bằng 0.
Sau đó, chúng tôi sẽ tính toán trước tần số của ký tự ở mọi giá trị chỉ mục. Sau đó, chúng tôi sẽ tìm tần suất của ký tự trong phạm vi bằng cách lấy tần suất xuất hiện ở chỉ mục l lấy ở chỉ mục r lấy.
Hãy lấy một ví dụ để hiểu vấn đề,
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int charFreq[100][26];
struct Query{
int l, r;
char ch;
};
void countCharFreq(string str, int size){
memset(charFreq, 0, sizeof(int));
for (int i = 0; i < size; i++){
charFreq[i][str[i] - 'a']++;
}
for (int i = 1; i < size; i++) {
for (int j = 0; j < 26; j++)
charFreq[i][j] += charFreq[i - 1][j] ;
}
}
int CalcCharFreq(Query queries){
return charFreq[queries.r][queries.ch - 'a'] - charFreq[queries.l][queries.ch - 'a'];
}
int main(){
string str = "tutorialspoint";
int size = str.length();
int Q = 2;
countCharFreq(str, size);
Query queries[Q];
queries[0].l = 1;
queries[0].r = 13;
queries[0].ch = 't';
queries[1].l = 4;
queries[1].r = 13;
queries[1].ch = 'i';
for(int i = 0; i<Q; i++)
cout<<"For Query "<<(i+1)<<": The frequency of occurrence of character '"<<queries[i].ch<<"' is " <<CalcCharFreq( queries[i])<<"\n";
return 0;
} Đầu ra
For Query 1: The frequency of occurrence of character 't' is 2 For Query 2: The frequency of occurrence of character 'i' is 2