344 反转字符串

思路：此题其实可以直接用库函数reserve来解决，但实际上这道题本意肯定不是要求我们用库函数的。我们可以用到双指针的办法，将首尾字符交换，直到两个指针相遇。

1.双指针

代码如下：

class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i = 0, j = s.size() - 1; i < s.size() / 2; i++, j--){
            swap(s[i], s[j]);
        }
    }
};

时间复杂度为O(n)

541 反转字符串 II

思路：这题和上题一样，只需要循环进行反转就可以，这题我们用了reserve函数，但我们也可以自己写reserve函数。

1.循环反转

代码如下：

class Solution {
public:
    string reverseStr(string s, int k) {
        for(int i = 0; i < s.size(); 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;
    }
};

时间复杂度为O(n)

剑指 Offer 05.替换空格

思路：这题两种做法，第一种我们需要占用额外空间，另创一个新字符串，第二种我们还是用双指针在原字符串更改。

1.新字符数组

代码如下：(这里我们python写)

class Solution(object):
    def replaceSpace(self, s):
        """
        :type s: str
        :rtype: str
        """
        res = []
        for c in s:
            if c == ' ':
                res.append("%20")
            else:
                res.append(c)
        return ''.join(res)

时间复杂度O(n)
空间复杂度O(n)

2.双指针

这里我们从后往前修改，这样时间复杂度会低一点

代码如下：

class Solution {
public:
    string replaceSpace(string s) {
        int size = s.size();
        int count = 0;
        for(int i = 0; i < size; i++){
            if (s[i] == ' ') {
                count++;
            }
        }
        s.resize(s.size() + count * 2);
        int newSize = s.size();
        for(int i = newSize - 1, j = size - 1; j < i; i--, j--){
            if(s[j] != ' '){
                s[i] = s[j];
            }else{
                s[i] = '0';
                s[i - 1] = '2'; 
                s[i - 2] = '%';
                i -= 2;
            }
        }
        return s;
    }
};

时间复杂度O(n)

151 翻转字符串里的单词

思路：这题其实用库函数很好解决，但是同样题目的本意肯定不是这样的。这道题难点就是怎么去除多余的空格，同样可以用指针来做。

1.指针法

class Solution {
public:
    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);
        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 + 1;
            }
        }
        return s;
    }
};

时间复杂度O(n)

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

思路：这题其实用substring就可以很容易解决，但是会产生额外空间，所以我们可以在原字符串上进行修改。

1.原地反转

代码如下：

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(), s.begin() + n);
        reverse(s.begin() + n, s.end());
        reverse(s.begin(), s.end());
        return s;
    }
};

时间复杂度为O(n)