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