在本文中，我們將探討在給定字串中找到包含K個不同元音字母的最長子字串的問題。可以使用不同的演算法在C 中解決這個問題。這個問題在電腦科學領域中經常遇到，特別是在文字處理和自然語言處理任務中。它考察了一個人操作字串和處理邊界情況的能力。
在C 領域中，類別std::string代表了字串資料類型。這個多功能的實體可以用於儲存和操作字元序列。
模板類別 std::vector 體現了動態數組的特性，允許調整數組大小並對封裝的元素執行一系列操作。
作為一個類別模板，std::unordered_map封裝了一個無序映射結構。它允許儲存單一鍵值對，其中鍵保持不匹配，可以使用這些不同的鍵來檢索值。
函數模板std::max傳回兩個值中的最大值。這個多功能機制可以方便地比較任何資料類型，只要>運算子被正確定義。
std::string std::vector std::unordered_map std::max
開始
初始化變數以儲存最長子字串及其長度。
迭代遍歷字串以找到具有K個不同元音的子字串。
比較子字串的長度，並相應地更新最長子字串及其長度。
重複步驟2和3，直到所有子字串都被評估。
傳回最長的子字串。
結束
方法1 - 暴力破解
#方法2 − 滑動視窗
此實作體現了一種暴力方法，用於發現具有精確k個唯一元音字母的字串的最長子字串。程式碼透過定義兩個輔助函數來啟動：is_vowel和has_k_distinct_vowels。
is_vowel函數接收一個單獨的字元作為輸入，並在字元是元音字母（例如'a'，'e'，'i'，'o'或'u'）時傳回真值，否則傳回假值。這個函數後來被用來確認一個字元是否是元音字母。
has_k_distinct_vowels函數接受一個字串和一個整數k作為輸入，並傳回一個真值，如果字串剛好包含k個唯一的母音字母，則傳回真值，否則傳回假值。此函數使用unordered_set來記錄字串中的母音字母，並計算字串中唯一母音字母的數量。
主要功能longest_substring_bruteforce接收一個字串和一個整數k作為輸入，並傳回字串中包含精確k個唯一元音字母的最長子字串。
這是透過利用兩個巢狀的for迴圈來遍歷字串的所有可能子字串來實現的。對於每個子字串，它呼叫has_k_distinct_vowels函數來驗證子字串是否恰好有k個唯一的元音字母。
如果當前子字串具有k個唯一的元音字母，並且比當前最長的子字串更廣泛，則當前子字串將變成新的最長子字串。
最後，程式碼輸入一個字串和一個整數k，呼叫longest_substring_bruteforce函數來找出具有k個唯一元音字母的最長子字串，並輸出結果。
#include <iostream>
#include <string>
#include <unordered_set>
bool is_vowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
bool has_k_distinct_vowels(const std::string &s, int k) {
std::unordered_set<char> vowel_set;
for (char c : s) {
if (is_vowel(c)) {
vowel_set.insert(c);
}
}
return vowel_set.size() == k;
}
std::string longest_substring_bruteforce(const std::string &s, int k) {
std::string longest_substring = "";
int max_len = 0;
for (int i = 0; i < s.size(); ++i) {
for (int j = i; j < s.size(); ++j) {
std::string current_substring = s.substr(i, j - i + 1);
if (has_k_distinct_vowels(current_substring, k) && current_substring.size() > max_len) {
longest_substring = current_substring;
max_len = current_substring.size();
}
}
}
return longest_substring;
}
int main() {
std::string input = "aeiaaioooaauuaeiu";
int k = 3;
std::string result = longest_substring_bruteforce(input, k);
std::cout << "Longest substring with " << k << " distinct vowels: " << result << std::endl;
return 0;
}
Longest substring with 3 distinct vowels: iaaioooaa
滑動視窗方法是一種用於解決電腦科學和演算法問題的技術。它用於在給定的輸入中查找滿足特定條件的特定模式，例如子字串或子數組。
在這種方法中，使用兩個指標來建立一個滑動窗口，該窗口透過輸入進行滑動。視窗的大小根據需要進行調整，以確保滿足所需的條件。演算法會追蹤目前視窗的屬性，例如不同元素的數量、元素的總和等。
is_vowel函數是一個幫助函數，如果給定的字元是元音字母（即a，e，i，o或u），則傳回true。
主要函數longest_substring_slidingwindow接受字串s和整數k作為輸入。它使用兩個指針left和right來創建一個滑動窗口，並遍歷字串。
使用無序映射 freq 來追蹤目前視窗中每個元音字母的頻率。當視窗中元音字母的頻率超過 k 時，將左指針向右移動，直到元音字母的頻率再次等於 k。目前視窗的長度計算為 right - left 1，如果大於迄今為止所見過的最大長度，則更新起始索引和長度。
最後，函數使用字串類別的substr方法傳回具有k個不同元音字母的最長子字串。
#include <iostream>
#include <string>
#include <unordered_map>
bool is_vowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
std::string longest_substring_slidingwindow(const std::string &s, int k) {
int left = 0, right = 0, max_len = 0, start = 0;
std::unordered_map<char, int> freq;
while (right < s.size()) {
char c = s[right];
if (is_vowel(c)) {
freq[c]++;
}
while (freq.size() > k) {
char left_char = s[left];
if (is_vowel(left_char)) {
freq[left_char]--;
if (freq[left_char] == 0) {
freq.erase(left_char);
}
}
left++;
}
if (freq.size() == k && (right - left + 1) > max_len) {
max_len = right - left + 1;
start = left;
}
right++;
}
return s.substr(start, max_len);
}
int main() {
std::string input = "aeiaaioooaauuaeiu";
int k = 3;
std::string result = longest_substring_slidingwindow(input, k);
std::cout << "Longest substring with " << k << " distinct vowels: " << result << std::endl;
return 0;
}
Longest substring with 3 distinct vowels: iaaioooaa
在本文中，我们讨论了两种方法来解决在给定字符串中找到包含K个不同元音字母的最长子串的问题。第一种方法是暴力法，而第二种方法是滑动窗口法。暴力法的时间复杂度为O(n^3)，使其成为更适合处理较大输入的解决方案。滑动窗口法由于其较低的时间复杂度，推荐用于解决这个问题。
以上是最長的具有K個不同元音字母的子串的詳細內容。更多資訊請關注PHP中文網其他相關文章！
