数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
