第四章字符串

● 344.反转字符串

● 541. 反转字符串II

● 卡码网：54.替换数字

● 151.翻转字符串里的单词

● 卡码网：55.右旋转字符串

1 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

1.1 思路：

在for循环里，使用swap函数，判断条件是字符串大小的前一半。

1.2 代码：

    // 1.反转字符串：使用swap()函数交换字符串中字符的位置
    void reverseString(vector<char> &s)
    {
        for (int i = 0, j = s.size() - 1; i < j; i++, j--)
        {
            swap(s[i], s[j]);
        }
    }

2 反转字符串II

给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。

如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

2.1 思路：

使用reverse函数翻转字符串

2.2 代码：

   // 2.1 反转字符串II
    string reverseStr1(string s, int k)
    {
        int n = s.size(), pos = 0;
        while (pos < n)
        {
            if (pos + k < n)
            {
                reverse(s.begin() + pos, s.begin() + pos + k);
            }
            else
                reverse(s.begin() + pos, s.end());
            pos += 2 * k;
        }
        return s;
    }
    // 2.2使用C++库函数reverse版本
    string reverseStr2(string s, int k)
    {
        int s_size = s.size();
        for (int i = 0; i < s_size - 1; i += 2 * k)
        {
            if (i + k <= s.size())
            {
                reverse(s.begin() + i, s.begin() + i + k);
            }
            else
            {
                reverse(s.begin() + i, s.end());
            }
            return s;
        }
    }
    // 2.3 自己实现reverse函数
    void reverseSelf(string &s, int start, int end)
    {
        for (int i = start, j = end; i < j; i++, j--)
        {
            swap(s[i], s[j]);
        }
    }
    string reverseStr3(string s, int k)
    {
        int s_size = s.size();
        for (int i = 0; i < s_size - 1; i += 2 * k)
        {
            if (i + k <= s.size())
            {
                reverseSelf(s, i, i + k);
            }
            else
            {
                reverseSelf(s, i, s_size - 1);
            }
            return s;
        }
    }

3 替换数字

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。

3.1 思路：

使用resize函数扩大空间，倒着插入number

3.2 代码：

   // 3. 替换数字
    pair<string, int> input()
    {
        string s;
        int count = 0;
        while (cin >> s)
        {

            int sOldSize = s.size();
            for (int i = 0; i < s.size(); i++)
            {
                if (s[i] >= '0' && s[i] <= '9')
                {
                    count++;
                }
            }
            if(cin.get()=='\n') break;
        }
        pair<string, int> a(s, count);
        return a;
    }
    string replaceNumber(string s, int count)
    {
        int sOldSize = s.size();
        cout << "sOldSize: " << sOldSize << endl;

       
        s.resize(s.size() + count * 5);
                
        int sNewSize = s.size();
        cout << "count: " << count << endl;        
        cout << "sNewSize: " << sNewSize << endl;
        for (int i = sNewSize - 1, j = sOldSize - 1; i >= 0; i--, j--)
        {
            if (s[j] > '9' || s[j] < '0')
            {
                s[i] = s[j];
            }
            else
            {
                s[i] = 'r';
                s[i - 1] = 'e';
                s[i - 2] = 'b';
                s[i - 3] = 'm';
                s[i - 4] = 'u';
                s[i - 5] = 'n';
                i -= 5;
            }
        }
        return s;
    }

4 翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。

代码：

   //4. 翻转字符串里的单词:3步走，先删除多余的空格；整体翻转；以空格为界限，部分反转
    void removeExtraSpaces(string& s) {
        int slow = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] != ' '){
                if(slow != 0){
                    s[slow++] = ' ';
                }
                while (i < s.size() && s[i] != ' ')
                {
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow);
    }

    string reverseWords(string s){
        removeExtraSpaces(s);
        reverseSelf(s, 0, s.size() - 1);
        int start = 0;
        for(int i = 0; i <= s.size(); i++){
            if(i == s.size() || s[i] == ' '){
                reverseSelf(s, start, i - 1);
                start = i + 1;
            }
        }
        return s;

    }

5 右旋字符串

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。

代码：

    //5. 右旋字符串：整体倒叙；把后面的部分再倒一次
    string rightReverse(string s, int k){
        reverse(s.begin(), s.end());
        if(k > s.size()){
            s = "error";
            return s;
        }
        reverse(s.begin() + k, s.end());
        reverse(s.begin(), s.begin() + k - 1);
        return s;
    }