C++实现字符串元音字母反转的两种方法

来自:网络
时间:2024-09-10
阅读:

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

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

示例

  • 输入:s = “hello”
    输出:“holle”
  • 输入:s = “leetcode”
    输出:“leotcede”

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

代码实现

class Solution {
public:
    string reverseVowels(string s) {
        vector<pair<int, char>> yuan;

        // 设置一个集合装元音字母,然后一个个判断,如果是直接放入yuan,然后再倒序
        set<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};

        for(int i = 0; i < s.size(); i++) {
            if(vowels.find(s[i]) != vowels.end()) {
                yuan.push_back({i, s[i]});
            }
        }
        reverse(yuan.begin(), yuan.end());

        for(int i = 0; i < yuan.size(); i++) {
            s[yuan[i].first] = yuan[yuan.size() - 1 - i].second;
        }

        return s;
    }
};

1. 如何在C++中存储数字和字符并支持翻转

在C++中,可以使用vector<pair<int, char>>来同时存储数字和字符。vector是一个动态数组,可以支持反转操作。如下所示:

vector<pair<int, char>> yuan;
yuan.push_back({index, character});
reverse(yuan.begin(), yuan.end());

2. 判断字符是否在列表中

在判断一个字符是否在列表中时,使用setfind方法虽然简洁。

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操作

C++实现字符串元音字母反转的两种方法

使用特判

C++实现字符串元音字母反转的两种方法

3. 巧妙的反转操作

使用vector<pair<int, char>>存储元音字符及其索引,并进行反转:

for(int i = 0; i < yuan.size(); i++) {
    s[yuan[i].first] = yuan[yuan.size() - 1 - i].second;
}

这个方法减少了对原始字符串的迭代次数,只需处理元音字符的数量,而不是整个字符串。

方法二:双指针法

双指针法是一种高效的解决方案。在需要反转字符串中的部分字符时,通过从两端向中间移动指针来找到需要交换的字符,避免了额外的空间开销。

代码实现

class Solution {
public:
    string reverseVowels(string s) {
        int i = 0, j = s.size() - 1;
        
        while (i < j) {
            if (!isVowel(s[i])) {
                i++;
            } else if (!isVowel(s[j])) {
                j--;
            } else {
                swap(s[i], s[j]);
                i++;
                j--;
            }
        }
        return s;
    }
    
    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';
    }
};

双指针法核心思路

双指针法是一种简洁高效的解决方案,通过在字符串两端同时移动指针来实现反转操作。以下是详细步骤:

初始化指针

  • i指向字符串开头。
  • j指向字符串结尾。

移动指针并交换元音

  • 当指针ij未相遇时,继续执行循环。
  • 如果i指向的字符不是元音,i右移。
  • 如果j指向的字符不是元音,j左移。
  • 如果ij指向的字符都是元音,则交换这两个字符,并分别移动指针ij

优点

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

总结

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

以上就是C++实现字符串元音字母反转的两种方法的详细内容,更多关于C++元音字母反转的资料请关注其它相关文章!

返回顶部
顶部