C++实现字符串元音字母反转的巧妙方法【数据结构、双指针】

C++实现字符串元音字母反转的巧妙方法

在处理字符串问题时，我们经常需要对其中的字符进行操作，例如反转、替换等。本文将详细讨论如何在C++中实现仅反转字符串中的所有元音字母，并返回结果字符串。元音字母包括’a’、‘e’、‘i’、‘o’、‘u’，且可能以大小写两种形式出现不止一次。我们将介绍两种方法：利用数据结构和双指针算法。

示例

• 输入：s = “hello”

  输出：“holle”

• 输入：s = “leetcode”

  输出：“leotcede”

  345. 反转字符串中的元音字母 - 力扣（LeetCode）

  方法一：利用数据结构存储元音位置和字符并反转

  代码实现

  class Solution {
  public:
      string reverseVowels(string s) {
          vector yuan;
          // 设置一个集合装元音字母，然后一个个判断，如果是直接放入yuan，然后再倒序
          set vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
          for(int i = 0; i  
  1. 如何在C++中存储数字和字符并支持翻转
   
  在C++中，可以使用vector来同时存储数字和字符。vector是一个动态数组，可以支持反转操作。如下所示：
   
  vector yuan;
  yuan.push_back({index, character});
  reverse(yuan.begin(), yuan.end());
   
  2. 判断字符是否在列表中
   
  在判断一个字符是否在列表中时，使用set的find方法虽然简洁。
   
  if(vowels.find(s[i]) != vowels.end())
   
  但由于set的查找复杂度为O(log n)，对于小规模查找来说，直接使用特判方法效率更高，如下所示：
   
  bool isVowel(char c) {
      return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || 
             c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
  }
   
  使用set_find操作
   
  使用特判
   
  3. 巧妙的反转操作
   
  使用vector存储元音字符及其索引，并进行反转：
   
  for(int i = 0; i  
  这个方法减少了对原始字符串的迭代次数，只需处理元音字符的数量，而不是整个字符串。
   
  方法二：双指针法
   
  双指针法是一种高效的解决方案。在需要反转字符串中的部分字符时，通过从两端向中间移动指针来找到需要交换的字符，避免了额外的空间开销。
   
  代码实现
   
  class Solution {
  public:
      string reverseVowels(string s) {
          int i = 0, j = s.size() - 1;
          
          while (i  
  双指针法核心思路
   
  双指针法是一种简洁高效的解决方案，通过在字符串两端同时移动指针来实现反转操作。以下是详细步骤：
   
   
  初始化指针：
   
    
  i指向字符串开头。
  j指向字符串结尾。
   
  移动指针并交换元音：
   
    
  当指针i和j未相遇时，继续执行循环。
  如果i指向的字符不是元音，i右移。
  如果j指向的字符不是元音，j左移。
  如果i和j指向的字符都是元音，则交换这两个字符，并分别移动指针i和j。
  优点
   
  

  • 空间复杂度低：双指针法在原地反转元音字符，不需要额外的存储空间。
  • 时间复杂度低：该方法仅需一次遍历，时间复杂度为O(n)，其中n是字符串的长度。

    总结

    在处理字符串元音反转的问题时，利用数据结构和双指针法都是有效的解决方案。数据结构方法通过存储元音的位置和字符来实现反转，而双指针法通过两端同时向中间移动指针来找到需要交换的字符。这两种方法各有优劣，具体选择取决于问题的规模和对空间复杂度的要求。