leetcode题记-344.反转字符串

题目

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 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)

题解

解法一(辣鸡解法)直接下标交换

1
2
3
4
5
6
7
8
9
10
11
12
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%的用户

解法二 双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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()函数,在底层上应该是有改进的,并且在使用的时候将自增运算运用得淋漓尽致,于是乎又加快了不少。

1
2
3
4
5
6
7
8
9
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层面进行运算的,可以说是速度特别的快了。

1
2
3
4
5
6
7
8
9
10
11
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%的用户

Author: SmallXeon
Link: https://hexo.chensmallx.top/2019/09/06/leetcode-344-reverseString/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
一些推广链接
几个便宜量大的小✈场: FASTLINK, YToo, 论坛邀请注册: ,
便宜量大但是稳定性不足的VPS: , 价格略贵但好用的VPN: , ,