● 344.反转字符串 ● 541. 反转字符串II ● 剑指Offer 05.替换空格 ● 151.翻转字符串里的单词 ● 剑指Offer58-II.左旋转字符串

反转字符串

双指针，头尾向中间移动交换两边的元素。

C++

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0;
        int right = s.size() - 1;
        while(left < right) {
            swap(s[left], s[right]);
            left++;
            right--;
        }
    }
};

C#

C#不自带swap库函数，自己写一个。

public class Solution {
    public void ReverseString(char[] s) {
        int left = 0;
        int right = s.Length - 1;
        while(left < right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++;
            right--;
        }
    }
}

反转字符串II

C++

用for控制循环比较方便，本题核心在如何使用反转，所以调reverse库函数即可。

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i+= 2 * k) {
            if (s.size() >= i + k) {
                reverse(s.begin() + i, s.begin() + i + k);
            } else if (s.size() < i + k) {
                reverse(s.begin() + i, s.begin() + s.size());
            }
        }
        return s;
    }
};

C#

C#的Reverse注意第三个参数是长度不是索引。

public class Solution {
    public string ReverseStr(string s, int k) {
        char[] s1 = s.ToCharArray(); 
        for (int i = 0; i < s1.Length; i += 2 * k) {
            if (s1.Length >= i + k) {
                Array.Reverse(s1, i, k);
            } else {
                Array.Reverse(s1, i, s.Length - i);
            }
        }
         return new string(s1);
    }
}

替换空格

暴力是O(n^2)，每个元素被重复移动多次，一步到位就可以O(n),先扩容字符串，再双指针分别从旧的长度尾和新的长度尾移动拷贝旧的内容，遇到空格就替换成%20，注意指针位置的初始化要在resize之前，要不然长度就变了。

C++

class Solution {
public:
    string replaceSpace(string s) {
        int cnt = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') cnt++;
        }
        int left = s.size() - 1;
        int right = s.size() + 2 * cnt - 1;
        s.resize(s.size() + 2 * cnt);
        while (left < right) {
            if (s[left] == ' ') {
                s[right] = '0';
                s[right - 1] = '2';
                s[right - 2] = '%';
                left--;
                right -= 3;
            } else {
                s[right] = s[left];
                left--;
                right--;
            }
        }
        return s;
    }
};

C#

C#里string不能直接risize并且元素不可以更改，得转换成char[],但这样空间复杂度变成了O(n),理解思想即可。

public class Solution {
    public string ReplaceSpace(string s) {
        int cnt = 0;
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == ' ') cnt++;
        }
        int left = s.Length - 1;
        int right = s.Length + 2 * cnt - 1;
        char []ss = s.ToCharArray();
        Array.Resize(ref ss, s.Length + 2 * cnt);
        while (left < right) {
            if(ss[left] == ' ') {
                ss[right] = '0';
                ss[right - 1] = '2';
                ss[right - 2] = '%';
                right -= 3;
                left--;
            } else {
                ss[right] = ss[left];
                left--;
                right--;
            }
        }
        return new string(ss);
    }
}

反转字符串里的单词

• 双指针先处理多余的空格，类似删除数组中多余的元素，需要额外注意的是如何处理连续的一个单词，方法是if判断到有字符，就while处理一直到字符结束，不要直接if判断边界，要处理i+1>size的溢出，模拟这个连续的过程就好。单词之间的空格是fast不管先过，遇到下一个单词slow再加空格，这样比较容易考虑。

• 处理完整个字符串反转，再把每个单词反转，还是双指针，只不过这时候slow记录的不再是新字符串了，而是要倒转的单词首个索引。

• 注意最后单词反转的时候fast指针循环要到size，考虑最后一个字符的情况。

class Solution {
public:
    string reverseWords(string s) {
        //双指针先处理多余空格
        int slow = 0;
        int fast = 0;
        while (fast < s.size()) {
            if (s[fast] != ' ') {
                if (slow != 0) {
                    s[slow++] = ' ';
                }
                while (fast < s.size() &&　s[fast] != ' ') {
                    s[slow++] = s[fast++];
                }
            }
            fast++;
        }
        s.resize(slow);
        //反转单词
        reverse(s.begin(), s.end());
        //双指针再遍历一遍反转单词
        slow = 0;
        fast = 0;
        while (fast <= s.size()) {
            if(fast == s.size() || s[fast] == ' ') {
                reverse(s.begin() + slow, s.begin() + fast);
                slow = fast + 1;
            }
            fast++;
        }
        
        return s;
    }

};

C#

注意Resize，reverse的API不同

public class Solution {
    public string ReverseWords(string s) {
        int slow = 0;
        int fast = 0;
        char[] a = s.ToCharArray();
        while (fast < a.Length) {
            if (a[fast] != ' ') {
                if (slow != 0) {
                    a[slow++] = ' ';
                }
                while (fast < a.Length && a[fast] != ' ') {
                    a[slow++] = a[fast++];
                }
            }
            fast++;
        }
        Array.Resize(ref a, slow);
        Array.Reverse(a, 0, a.Length);
        slow = 0;
        fast = 0;
        for (fast = 0; fast <= a.Length; fast++) {
            if (fast == a.Length || a[fast] == ' ' ) {
                Array.Reverse(a, slow, fast - slow);
                slow = fast + 1;
            }
        }
        return new string(a);
        
    }
}

左旋转字符串

局部反转加全局反转。

1. 反转区间为前n的子串
2. 反转区间为n到末尾的子串
3. 反转整个字符串

C++

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

C#

public class Solution {
    public string ReverseLeftWords(string s, int n) {
        char[] a = s.ToCharArray();
        Array.Reverse(a, 0, n);
        Array.Reverse(a, n, a.Length - n);
        Array.Reverse(a, 0, a.Length);
        return new string(a);
    }
}

总结

此时我们已经反转好多次字符串了，来一起回顾一下吧。

在这篇文章344.反转字符串 (opens new window)，第一次讲到反转一个字符串应该怎么做，使用了双指针法。

然后发现541. 反转字符串II (opens new window)，这里开始给反转加上了一些条件，当需要固定规律一段一段去处理字符串的时候，要想想在for循环的表达式上做做文章。

后来在151.翻转字符串里的单词 (opens new window)中，要对一句话里的单词顺序进行反转，发现先整体反转再局部反转 是一个很妙的思路。

左旋转字符串则是先局部反转再整体反转，与151.翻转字符串里的单词 (opens new window)类似，但是也是一种新的思路。

二刷

反转字符串

#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0;
        int right = s.size() - 1;
        while (left <= right) {
            char temp = s[right];
            s[right] = s[left];
            s[left] = temp;
            left++;
            right--;
        }
        for (char it : s) {
            cout << it <<" ";
        }
    }
};

int main() {
    vector<char> ss;
    char temp;
    while (cin >> temp) {
        ss.push_back(temp);
    }
    Solution s;
    s.reverseString(ss);
    return 0;
}

反转字符串2

善用API，秒了。

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i = i + 2 * k) {
            int end = i + k < s.size() ? i + k : s.size();
            reverse(s.begin() + i, s.begin()+ end);
        }
        return s;
    }
};

替换空格

leetcode没了，换牛客，注意下resize的API。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string replaceSpace(string s) {
        int blankCnt = 0;
        for (char it : s) {
            if (it == ' ') {
                blankCnt++;
            }
        }
        int oldSize = s.size() - 1;
        s.resize(s.size() + blankCnt * 2);
        int right = s.size() - 1;
        for (int i = oldSize; i >= 0; i--) {
            if (s[i] == ' ') {
                s[right--] = '0';
                s[right--] = '2';
                s[right--] = '%';
            } 
            else {
                s[right--] = s[i];
            }
        }   
        return s;
    }
};

反转字符串中的单词

class Solution {
public:
    string reverseWords(string s) {
        //删除前导0
        int slow = 0;
        int fast = 0;
        while (fast < s.size()) {
            if (s[fast] != ' ') {
                if (slow != 0) {
                    s[slow++] = ' ';
                }
                while (fast < s.size() && s[fast] != ' ') {
                    s[slow] = s[fast];
                    slow++;
                    fast++;
                }
            }
            fast++;
                 
        }
        s.resize(slow);
        //反转数组
        //先整体反转一次
        reverse(s.begin(), s.end());
        slow = 0;
        fast = 0;
        while (fast <= s.size()) {
            if (fast == s.size() || s[fast] == ' ') {
                reverse(s.begin() + slow, s.begin() + fast);
                slow = fast + 1;
            }
            fast++;
        }
        return s;
    }
};

左旋转字符串

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param n int整型 
     * @return string字符串
     */
    string LeftRotateString(string str, int n) {
        // write code here
        int oldSize = str.size();
        str.resize(oldSize + n);
        for (int i = 0 ; i < n; i++) {
            str[oldSize + i] = str[i];
        }
        for (int i = 0; i <= oldSize; i++) {
            str[i] = str[i + n];
        }
        str.resize(oldSize);
        return str;
    }
};