代码随想录算法训练营第8天 | 344.反转字符串，541.反转字符串II，剑指Offer 05.替换空格，151.翻转字符串里的单词，剑指Offer58-II.左旋转字符串

344.反转字符串

代码随想录链接

题目

LeetCode-344

将一个字符串中的字符翻转。只能在函数中使用\(O(1)\)的额外空间。

自己的想法

使用\(O(1)\)的空间意味着，对于字符串的逆转操作只能原地进行。

因为本题的关键点就在于逆转操作，故不可以直接使用reverse函数完成。

使用双指针法，将左右指针分别指向字符串的起始位置和末尾，交换两个指针指向的字符，并将指针向中间靠拢。

解法

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size() - 1;     // 初始化左右指针
        while (left < right) {                  // 左右指针结束循环条件
            swap(s[left], s[right]);            // 交换左右指针的值
            left++;                             // 左右指针分别向中间移动
            right--;
        }
    }
};

时间复杂度为\(O(n)\)，空间复杂度为\(O(1)\)。

541.反转字符串II

代码随想录链接

题目

LeetCode-541

给定一个字符串和一个正整数k，对于每2k的字符，翻转前k个字符。若剩余不到k个字符，则全部翻转；若剩余字符数大于等于k但小于2k，则翻转前k个字符。

自己的想法

使用一个for循环来确定每2k个字符所形成的字符串的左侧起始区间，判断自该位置起始的剩余字符串的长度是否大于等于k，若大于等于k，则翻转自该位置起的k个字符所形成的字符串；若剩余长度小于k，则翻转剩余字符。

解法

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += 2 * k) {         // 确定每2k个字符形成的字符串的起始位置
            if (i + k <= s.size()) {                        // 若剩余字符个数大于等于k
                reverse(s.begin() + i, s.begin() + i + k);  // 翻转k个字符
            } else {                                        // 否则就翻转剩下的字符
                reverse(s.begin() + i, s.end());
            }
        }
        return s;
    }
};

剑指Offer 05.替换空格

代码随想录链接

题目

剑指 Offer 05.替换空格

将字符串中的空格替换为"%20"。

自己的想法

如果使用额外的新数组作为结果进行返回，题目就很简单，遍历数组即可。使用\(O(1)\)的空间复杂度才使得这个题目有难度。

这个题目类似于LeetCode-27.移除元素，可以使用双指针方法来进行替换。若要原地替换，首先统计字符串中有多少个空格，计算出新的字符串应该有的长度，对原字符串进行长度调整。然后再使用两个指针，指针A指向原字符串的末尾，指针B指向调整后的字符串的末尾。将指针A向前移动，若遇见一个空格，则在指针B指向的位置依次向前插入'0', '2', '%'；若遇见空格之外的字符，则直接拷贝至指针B指向的位置。

解法一

暴力法

class Solution {
public:
    string replaceSpace(string s) {
        string result;
        for (char c: s) {
            if (c == ' ') {
                result.append("%20");
            } else result.push_back(c);
        }
        return result;
    }
};

解法二

class Solution {
public:
    string replaceSpace(string s) {
        int blankCount = 0;
        for (char c: s) {           // 统计空格的个数
            if (c == ' ') {
                blankCount++;
            } 
        }
        int oldPointer = s.size() - 1;                  // 指针A指向原字符串的末尾
        s.resize(2 * blankCount + s.size());            // 扩展字符串至替换后应该有的长度
        int newPointer = s.size() - 1;                  // 指针B指向新字符串的末尾
        while (blankCount) {                            // 当空格没有被替换完毕时
            if (s[oldPointer] == ' ') {                 // 如果指针A遇到了一个空格
                s[newPointer--] = '0';                  // 依次插入替换的字符
                s[newPointer--] = '2';
                s[newPointer--] = '%';
                blankCount--;                           // 空格计数器减1
                oldPointer--;                           // 指针A向前移动
            } else s[newPointer--] = s[oldPointer--];   // 遇到的不是空格，就直接拷贝原字符
        }

        return s;
    }
};

时间复杂度为\(O(n)\)，空间复杂度为\(O(1)\)。

151.翻转字符串里的单词

代码随想录链接

题目

LeetCode-151

将字符串中的单词进行翻转，而单词保持原来的状态。同时去除字符串前后的空格和连续的多余空格。

自己的想法

字符串中的一些部分翻转而另外一些保持原形，就可以考虑使用先整体翻转再部分翻转来解决。

在这个题目中，可以先去除多余的空格，再将整个字符串翻转，最后再以单词为分区，进行分区内的翻转。

解法

class Solution {
public:
    string reverseWords(string s) {
        int fast = 0, slow = 0;                                     // 同27.移除元素，使用双指针法移除元素
        while (s[fast] == ' ' && fast < s.size()) fast++;           // 移除开头的空格
        while (fast < s.size()) {                                   // 每碰见一个空格，就像慢指针的位置写入一个空格，并将快指针移至下一个不为空格的位置
            if (s[fast] == ' ') {
                s[slow++] = ' ';
                while (s[fast] == ' ' && fast < s.size()) fast++;
            } else {
                s[slow++] = s[fast++];                              // fast指针不指向空格时，拷贝fast指针指向的内容至slow指针
            }
        }
        if (s[slow - 1] == ' ') {                                   // 去除末尾可能多出来的一个空格
            slow--;
        }
        s.resize(slow);                                             // 调整s的大小，该大小为去除多余空格之后的字符串大小
        reverse(s.begin(), s.end());                                // 翻转整个字符串
        int start = 0;                                              // 标记每个单词的起始位置
        for (int i = 0; i <= s.size(); i++) {                       // 遍历字符串，找单词之间的空格
            if (i == s.size() || s[i] == ' ') {                     // 遇到了空格或者字符串末尾
                reverse(s.begin() + start, s.begin() + i);          // 翻转[start, i)区间的字符串
                start = i + 1;                                      // 移动单词起始位置至空格后的字符
            }
        }
        return s;
    }
};

剑指 Offer 58-II.左旋转字符串

代码随想录链接

题目

剑指 Offer 58-II.左旋转字符串

给定一个字符串和一个整数k，将前k位的字符移至字符串末尾。

自己的想法

和上面的题相似，可以采用先整体翻转再局部翻转的方法解决。先将整个字符串进行翻转，再翻转\([0, size - k)\)区间的字符，最后反转\([size - k, size)\)部分即可。

解法

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(), s.end());            // 翻转整个字符串
        reverse(s.begin(), s.end() - n);        // 翻转[0, size - k)
        reverse(s.end() - n, s.end());          // 翻转[size - k, size)
        return s;
    }
};