题目

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

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

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

示例 1：

输入：[“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]

示例 2：

输入：[“H”,”a”,”n”,”n”,”a”,”h”]
输出：[“h”,”a”,”n”,”n”,”a”,”H”]

来源：力扣（LeetCode）

题解

解法一（辣鸡解法）直接下标交换

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

结果

执行用时 : 72 ms, 在所有 C++ 提交中击败了54.97%的用户
内存消耗 : 15.2 MB, 在所有 C++ 提交中击败了79.02%的用户

解法二 双指针法

class Solution {
public:
    inline void swap(char& x, char& y) {
        char c = x;
        x = y;
        y = c;
    }
    void reverseString(vector<char>& s) {
        int i = 0, j = s.size() - 1;
        while (i < j) {
            swap(s[i], s[j]);
            i++, j--;
        }
    }
};

结果

执行用时 : 64 ms, 在所有 C++ 提交中击败了85.40%的用户
内存消耗 : 15.1 MB, 在所有 C++ 提交中击败了90.38%的用户

双指针的确比直接诶计算下标快了不少，毕竟在算加减的时候双指针法只用了两个基本的加减，而直接计算下标（算上改变i）则需要5此加减法，消耗了两倍多的计算量。

优化的双指针

优化一 C++ swap

这里使用了c++自带的swap()函数，在底层上应该是有改进的，并且在使用的时候将自增运算运用得淋漓尽致，于是乎又加快了不少。

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

结果

执行用时 : 60 ms, 在所有 C++ 提交中击败了94.45%的用户
内存消耗 : 15 MB, 在所有 C++ 提交中击败了94.68%的用户

优化二 位运算

这算是奇技淫巧的一种了，就是两个变量来回异或就可以交换数据，而且是从bit层面进行运算的，可以说是速度特别的快了。

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

结果

执行用时 : 52 ms, 在所有 C++ 提交中击败了99.76%的用户
内存消耗 : 15.3 MB, 在所有 C++ 提交中击败了75.25%的用户