この記事では、指定された文字列内に K 個の異なる母音を含む最長の部分文字列を見つける問題を検討します。この問題は、C でさまざまなアルゴリズムを使用して解決できます。この問題は、コンピュータ サイエンスの分野、特にテキスト処理や自然言語処理タスクで頻繁に発生します。文字列を操作し、特殊なケースに対処する人の能力を検査します。
###文法###テンプレート クラス std::vector は動的配列の特性を具体化しており、配列のサイズを調整したり、カプセル化された要素に対して一連の操作を実行したりできます。
クラス テンプレートとして、std::unowned_map は順序なしマッピング構造をカプセル化します。これにより、キーが不一致のままの単一のキーと値のペアを保存でき、これらの異なるキーを使用して値を取得できます。
関数テンプレート std::max は、2 つの値の最大値を返します。この多用途メカニズムにより、> 演算子が正しく定義されていれば、あらゆるデータ型を簡単に比較できます。
リーリー ###アルゴリズム#########始める######
文字列を反復処理して、K 個の異なる母音を持つ部分文字列を見つけます。
部分文字列の長さを比較し、それに応じて最長の部分文字列とその長さを更新します。
すべての部分文字列が評価されるまで、手順 2 と 3 を繰り返します。
最長の部分文字列を返します。
- ブルート フォース クラッキング
この実装は、正確に k 個の一意の母音を持つ文字列の最長部分文字列を検出するための総当り手法を具体化しています。コードは、is_vowel と has_k_distinct_vowels という 2 つのヘルパー関数を定義することから始まります。 Example
の中国語訳は次のとおりです:is_vowel 関数は 1 つの文字を入力として受け取り、その文字が母音 (「a」、「e」、「i」、「o」、「u」など) の場合は true を返し、それ以外の場合は false を返します。価値。この関数は、後に文字が母音であるかどうかを判断するために使用されました。 has_k_distinct_vowels 関数は、文字列と整数 k を入力として受け入れ、文字列にちょうど k 個の一意の母音が含まれる場合は true 値を返し、それ以外の場合は false 値を返します。この関数は、unordered_set を使用して文字列内の母音を記録し、文字列内の一意の母音の数をカウントします。
現在の部分文字列に k 個の一意の母音があり、現在の最長部分文字列よりも幅が広い場合、現在の部分文字列が新しい最長部分文字列になります。
スライディング ウィンドウ法は、コンピューター サイエンスとアルゴリズムの問題を解決するために使用される手法です。これは、特定の入力内で特定の基準を満たす、部分文字列や部分配列などの特定のパターンを検索するために使用されます。
このメソッドでは、2 つのポインターを使用して、入力内をスライドするスライディング ウィンドウを作成します。ウィンドウのサイズは、必要な条件が確実に満たされるように、必要に応じて調整されます。このアルゴリズムは、個別の要素の数、要素の合計など、現在のウィンドウのプロパティを追跡します。
Example
の中国語訳は次のとおりです:Example
is_vowel 関数は、指定された文字が母音 (つまり、a、e、i、o、または u) の場合に true を返すヘルパー関数です。
メイン関数longest_substring_slidingwindowは、文字列sと整数kを入力として受け入れます。左右の 2 つのポインターを使用してスライディング ウィンドウを作成し、文字列を反復処理します。
#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 中国語 Web サイトの他の関連記事を参照してください。