C++實現(xiàn)字符串元音字母反轉的兩種方法

更新時間：2024年07月19日 10:40:18 作者：修煉室

在處理字符串問題時,我們經(jīng)常需要對其中的字符進行操作,例如反轉、替換等,本文將詳細討論如何在C++中實現(xiàn)僅反轉字符串中的所有元音字母,并返回結果字符串,需要的朋友可以參考下

C++實現(xiàn)字符串元音字母反轉的巧妙方法

在處理字符串問題時，我們經(jīng)常需要對其中的字符進行操作，例如反轉、替換等。本文將詳細討論如何在C++中實現(xiàn)僅反轉字符串中的所有元音字母，并返回結果字符串。元音字母包括’a’、‘e’、‘i’、‘o’、‘u’，且可能以大小寫兩種形式出現(xiàn)不止一次。我們將介紹兩種方法：利用數(shù)據(jù)結構和雙指針算法。

示例

輸入：s = “hello”
輸出：“holle”
輸入：s = “leetcode”
輸出：“leotcede”

方法一：利用數(shù)據(jù)結構存儲元音位置和字符并反轉

代碼實現(xiàn)

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++中存儲數(shù)字和字符并支持翻轉

在C++中，可以使用vector<pair<int, char>>來同時存儲數(shù)字和字符。vector是一個動態(tài)數(shù)組，可以支持反轉操作。如下所示：

vector<pair<int, char>> 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)，對于小規(guī)模查找來說，直接使用特判方法效率更高，如下所示：

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<pair<int, char>>存儲元音字符及其索引，并進行反轉：

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

這個方法減少了對原始字符串的迭代次數(shù)，只需處理元音字符的數(shù)量，而不是整個字符串。

方法二：雙指針法

雙指針法是一種高效的解決方案。在需要反轉字符串中的部分字符時，通過從兩端向中間移動指針來找到需要交換的字符，避免了額外的空間開銷。

代碼實現(xiàn)

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';
    }
};

雙指針法核心思路

雙指針法是一種簡潔高效的解決方案，通過在字符串兩端同時移動指針來實現(xiàn)反轉操作。以下是詳細步驟：

初始化指針：

i指向字符串開頭。
j指向字符串結尾。

移動指針并交換元音：

當指針i和j未相遇時，繼續(xù)執(zhí)行循環(huán)。
如果i指向的字符不是元音，i右移。
如果j指向的字符不是元音，j左移。
如果i和j指向的字符都是元音，則交換這兩個字符，并分別移動指針i和j。

優(yōu)點

空間復雜度低：雙指針法在原地反轉元音字符，不需要額外的存儲空間。時間復雜度低：該方法僅需一次遍歷，時間復雜度為O(n)，其中n是字符串的長度。

總結

在處理字符串元音反轉的問題時，利用數(shù)據(jù)結構和雙指針法都是有效的解決方案。數(shù)據(jù)結構方法通過存儲元音的位置和字符來實現(xiàn)反轉，而雙指針法通過兩端同時向中間移動指針來找到需要交換的字符。這兩種方法各有優(yōu)劣，具體選擇取決于問題的規(guī)模和對空間復雜度的要求。

以上就是C++實現(xiàn)字符串元音字母反轉的兩種方法的詳細內(nèi)容，更多關于C++元音字母反轉的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: