資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究包含 K 個不同母音的最長子字串
在本文中，我們將探討在一個給定字串中查詢包含 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 - 滑動視窗
方法 1：- 暴力法
該實現體現了一個使用暴力法來發現具有精確 k 個唯一母音的字串的最長子字串的過程。程式碼首先定義了兩個輔助函式：is_vowel 和 has_k_distinct_vowels。
示例
is_vowel 函式接收單個字元作為輸入，如果字元是母音（例如 'a'、'e'、'i'、'o' 或 'u'），則返回真值，否則返回假值。此函式稍後用於確認字元是否為母音。
has_k_distinct_vowels 函式接收一個字串和一個整數 k 作為輸入，如果字串恰好包含 k 個唯一母音，則返回真值，否則返回假值。此函式使用無序集合來記錄字串中的母音並計算字串中唯一母音的數量。
主函式 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
方法 2：- 滑動視窗
滑動視窗方法是一種用於解決計算機科學和演算法中問題的技術。它用於在給定的輸入中查詢滿足特定條件的特定模式，例如子字串或子陣列。
在這種方法中，使用兩個指標建立一個視窗，該視窗在輸入中滑動。根據需要調整視窗的大小以確保它滿足所需的條件。該演算法跟蹤當前視窗的屬性，例如不同元素的數量、元素的總和等。
示例
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)，這使得它對於較大的輸入而言是一個更有效的解決方案。由於其較低的時間複雜度，建議使用滑動視窗方法來解決此問題。
298 次瀏覽
