数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 子字符串中字符频率查询
在这个问题中，我们给定一个字符串。并且有 Q 个查询，每个查询包含两个整数 l 和 r 以及字符 ch。我们的任务是创建一个程序，用 C++ 解决子字符串中字符频率的查询。
问题描述：在这里，对于每个查询，我们将找到字符 ‘ch’ 在子字符串 str[l...r] 中出现的频率。
让我们举个例子来理解这个问题，
输入
str = “tutorialspoint” Q = 2 0 6 t 5 13 i
输出
2 2
解释
对于查询 1 - 子字符串是“tutoria”，字符 t 出现 2 次。
对于查询 2 - 子字符串是“ialspoint”，字符 i 出现 2 次。
解决方案方法
解决这个问题的简单直接的方法是，对于每个查询，遍历从 l 到 r 的字符串，并统计字符串中字符 ch 出现的次数。
程序说明我们解决方案的工作原理，
示例
#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;
}输出
For Query 1: The frequency of occurrence of character 't' is 2 For Query 2: The frequency of occurrence of character 'i' is 2
另一种方法来解决这个问题是使用预计算数组。在这里，我们将创建一个二维数组，它将存储字符到特定索引处的频率，即 freq[3][2] 将存储索引 2 处字符 ‘c’ 的频率。最初，所有频率都为 0。
然后，我们将预先计算每个索引值的字符频率。之后，我们将通过从索引 r 处的出现频率中减去索引 l 处的出现频率来找到该范围内字符的频率。
让我们举个例子来理解这个问题，
示例
#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;
}输出
For Query 1: The frequency of occurrence of character 't' is 2 For Query 2: The frequency of occurrence of character 'i' is 2
更新于: 2020-09-09
126 次查看
广告