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

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

示例

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

方法一：利用數(shù)據(jù)結(jié)構(gòu)存儲元音位置和字符并反轉(zhuǎn)

代碼實(shí)現(xiàn)

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

        // 設(shè)置一個(gè)集合裝元音字母，然后一個(gè)個(gè)判斷，如果是直接放入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ù)字和字符并支持翻轉(zhuǎn)

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

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

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

在判斷一個(gè)字符是否在列表中時(shí)，使用set的find方法雖然簡潔。

if(vowels.find(s[i]) != vowels.end())

但由于set的查找復(fù)雜度為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. 巧妙的反轉(zhuǎn)操作

使用vector<pair<int, char>>存儲元音字符及其索引，并進(jìn)行反轉(zhuǎn)：

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

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

方法二：雙指針法

雙指針法是一種高效的解決方案。在需要反轉(zhuǎn)字符串中的部分字符時(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';
    }
};

雙指針法核心思路

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

初始化指針：

• i指向字符串開頭。
• j指向字符串結(jié)尾。

移動指針并交換元音：

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

優(yōu)點(diǎn)

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

總結(jié)

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

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

最新評論