C++ 实现最长的宝石串 |21xrx.com

C++ 实现最长的宝石串

2023-07-06 17:10:29 深夜i -- --

C++ 最长宝石串

最长宝石串是一个经典的计算机问题，它需要在一个字符串中找到最长的一段子串，使得该子串只包含指定的一些字符。在 C++ 中，我们可以使用哈希表来实现这个算法，下面就让我们来看一下如何实现最长宝石串的解决方案。

首先，我们需要定义一个哈希表来存储每个字符出现的次数。我们可以使用无序_map来实现这个哈希表。然后，我们需要定义两个指针：start 和 end，来指示当前子串的起始位置和结束位置。我们还需要定义一个变量来保存当前最长宝石串的长度。

接下来，我们可以使用 while 循环来遍历整个字符串。对于每个字符，我们可以将其加入哈希表中，并将 end 指针向右移动。如果当前子串中包含了所有宝石字符，我们可以更新最长宝石串的长度，并将 start 指针向右移动，直到子串中不再包含所有宝石字符为止。

最后，我们可以返回最长宝石串的长度作为答案。下面是一个完整的 C++ 代码示例：


#include <unordered_map>
#include <string>
int lengthOfLongestGemstoneString(std::string s, std::string gems) {
  std::unordered_map<char, int> gemCount;
  int start = 0, end = 0, maxLen = 0, cnt = 0;
  for (const auto& gem : gems) {
    gemCount[gem]++;
  }
  while (end < s.size()) {
    if (gemCount.find(s[end]) != gemCount.end() && --gemCount[s[end]] >= 0) {
      cnt++;
    }
    while (cnt == gems.size()) {
      maxLen = std::max(maxLen, end - start + 1);
      if (++gemCount[s[start]] > 0)
        cnt--;
      
      start++;
    }
    end++;
  }
  return maxLen;
}

在这个示例代码中，我们使用了内置函数 std::max 来更新最长宝石串的长度。在 while 循环中，我们使用两个指针 start 和 end 来遍历整个字符串，并使用 gemCount 哈希表来记录当前子串中宝石字符出现的次数。在每个 while 循环中，我们首先将 end 指针右移，并检查新的字符是否为宝石字符，如果是，则将其从 gemCount 哈希表中减去一个，并递增 cnt 变量。当 cnt 递增到等于 gems.size() 时，说明当前子串包含了所有宝石字符，我们可以更新最长宝石串的长度，并将 start 指针右移，直到子串不再包含所有宝石字符为止。

在这个例子中，我们使用了字符串和哈希表这两个常用的 C++ 数据结构来实现最长宝石串算法。这个解决方案可以通过 LeetCode 测试，并获得了不错的运行时间和内存占用表现。在实际的开发中，我们也可以使用类似的思路来解决各种数据处理和搜索问题。

上一篇: idea打包java可执行jar包

下一篇: C++中的count函数解析

评论区

()

相似文章