資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學包含最多 X 個不同母音的長度為 K 的子字串計數
在這個問題中，我們需要找到長度為 K 的子字串的總數，這些子字串最多包含 X 個不同的母音。我們可以透過兩種不同的方式解決這個問題。第一種方法是獲取所有子字串，並計算長度為 K 的每個子字串中不同的母音數量。第二種方法是使用 map 資料結構並跟蹤特定子字串中不同母音的數量。
問題陳述– 我們給定長度為 N 的字串 str。該字串僅包含字母字元。此外，我們還給定 K 和 X 兩個正整數。我們需要找到長度為 K 的不同子字串的總數，這些子字串最多包含 X 個不同的母音。
示例
輸入– str = ‘point’，K = 3，X = 2
輸出– 3
解釋– 長度為 3 且最多包含 2 個不同母音的子字串為：
字串 ‘poi’ 包含 2 個母音。
字串 ‘oin’ 包含 2 個母音。
字串 ‘int’ 包含 1 個母音。
輸入– str = ‘sdfgh’，K = 3，X = 2
輸出– 0
解釋– 該字串不包含任何母音，因此輸出為零。
輸入– str = ‘aeiou’，K = 2，X = 2
輸出– 4
解釋– 長度為 2 且最多包含 2 個不同母音的子字串為：‘ae’，‘ei’，‘io’ 和 ‘ou’。
方法 1
在這種方法中，我們將從給定字串中獲取每個長度為 K 的子字串。之後，我們將檢查子字串中不同母音的數量，並根據子字串包含的母音總數返回結果值。
演算法
初始化 ‘cnt’ 和 ‘len’ 變數。
開始遍歷字串，從第 0 個索引遍歷到 len – k 索引。
使用 substr() 方法獲取從索引 i 開始長度為 K 的子字串。
使用 countDistVowels() 函式計算子字串中不同的母音數量。
在 countDistVowels() 函式中，使用 map 儲存特定母音的存在。
從 map 中訪問 a、e、i、o 和 u 鍵的值，並返回它們的和。
如果子字串中不同母音的總數小於 K，則將 ‘cnt’ 值加 1。
當迴圈的所有迭代完成後，返回 ‘cnt’ 值。
示例
#include <bits/stdc++.h>
using namespace std;
int countDistVowels(string str){
int dist = 0;
int len = str.length();
// map to store the presence of vowels
unordered_map<char, int> mp;
// insert vowels in the map
for (int i = 0; i < len; i++){
mp[str[i]] = 1;
}
// return the count of distinct vowels in a string
return mp['a'] + mp['e'] + mp['i'] + mp['o'] + mp['u'];
}
int countSubStr(string str, int K, int X){
// to store the total substring following the given condition
int cnt = 0;
int len = str.size();
for (int i = 0; i <= len - K; i++){
// get a substring of length K
string s = str.substr(i, K);
// If contDistVowels() function returns value less than X, increment cnt by 1.
if (countDistVowels(s) <= X){
cnt++;
}
}
return cnt;
}
int main(void){
string str = "point";
int K = 3, X = 2;
cout << "The number of a substring of length K containing at most X distinct vowels are " << countSubStr(str, K, X);
return 0;
}
輸出
The number of a substring of length K containing at most X distinct vowels are 3
時間複雜度 – O(N*K)，因為我們在每個子字串中計算不同的母音。
空間複雜度 – O(K)，因為我們儲存長度為 K 的子字串。
方法 2
此方法使用滑動視窗技術來解決問題。我們可以計算第一個視窗中不同母音的總數，然後，當我們更新視窗中的字元時，我們繼續更新不同母音的數量。
演算法
定義 ‘vow’ 變數並初始化為零。另外，定義 map 來儲存母音頻率。
將字串轉換為小寫。
計算從索引 0 開始的長度為 K 的第一個子字串中不同母音的總數。
如果 ‘vow’ 的值小於或等於 X，則將 ‘cnt’ 值初始化為 1。否則為 0。
從第 1 個索引遍歷到 len – k 索引。
如果第 (I – 1) 個字元是母音，則將 ‘vow’ 的值減 1，並在 map 中更新其頻率。
我們需要將第 (I – 1 + K) 個字元插入到當前視窗中。如果它是母音，並且它在 map 中的頻率為零，則將 ‘vow’ 加 1，並在 map 中更新頻率，因為它是在當前視窗中不同的母音。
如果 ‘vow’ 的值小於 X，則將 ‘cnt’ 加 1。
返回 ‘cnt’ 值加 1。
示例
#include <bits/stdc++.h>
using namespace std;
// to check given character is vowel or not
bool isVowel(char ch) {
return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
// function to count the number of substrings of length k containing at most k vowels
int countSubStr(string alpha, int K, int X) {
// to store the count of vowels
int vow = 0;
// creating an unordered map to store the count of vowels
unordered_map<char, int> mp;
// convert string to lowercase
transform(alpha.begin(), alpha.end(), alpha.begin(), ::tolower);
// store total distinct vowels in the string of length k
for (int i = 0; i < K; i++) {
if (isVowel(alpha[i]) && mp[alpha[i]] == 0) {
vow++;
mp[alpha[i]]++;
}
}
// If first substring contains at most x vowels, then increment cnt by 1
int cnt = vow <= X ? 1 : 0;
for (int i = 1; i <= alpha.length() -K; i++) {
// remove i-1th character from the current window
if (isVowel(alpha[i - 1])) {
vow--;
mp[alpha[i - 1]]--;
}
// Insert (i - 1 + K)th character
if (isVowel(alpha[i - 1 + K]) && mp[alpha[i - 1 + K]] == 0) {
vow++;
mp[alpha[i - 1 + K]]++;
}
if (vow <= X)
cnt++;
}
return cnt;
}
int main(void) {
string str = "point";
int K = 3, X = 2;
cout << "The number of a substring of length K containing at most X distinct vowels are " << countSubStr(str, K, X);
return 0;
}
輸出
The number of a substring of length K containing at most X distinct vowels are 3
時間複雜度 – O(N)，因為我們遍歷字串。
空間複雜度 – O(1)，因為我們使用常量空間。
我們使用兩種方法解決了這個問題。第二種方法使用滑動視窗技術來最佳化程式碼。程式設計師可以嘗試計算包含最多 X 個不同母音的任意長度的子字串的總數，並透過此類問題進行更多練習。
128 次瀏覽
