周浦网站建设公司跨界营销案例

反转字符串

本节对应代码随想录中：代码随想录，讲解视频：字符串基础操作！ | LeetCode：344.反转字符串_哔哩哔哩_bilibili

习题

题目链接：344. 反转字符串 - 力扣（LeetCode）

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

双指针

作为数组的第一题，这题还是比较简单的。反转字符串其实就是原来第一个字符变成最后一个字符，原来第二个字符变成倒数第二个字符，以此类推。那其实就是将第一个与最后一个字符交换，将第二个与倒数第二个字符交换，以此类推。并且我们只需要遍历字符串一半的长度就行交换即可。

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

• 时间复杂度：O($n$)。有一个 for 循环，它的迭代次数是数组大小的一半，即 O(n/2)，swap 函数交换了两个元素的值，其时间复杂度为 O(1)。因此，这个函数的时间复杂度为 O(n/2 * 1)，也就是 O(n)
• 空间复杂度：O($1$)。只使用了常量级别的额外空间存储变量 i、j 和 size，因此空间复杂度为 O(1)

对于本题，其实使用库函数 reverse 就能解题，但显然本题并不是考察库函数的使用，面试的时候更不会如此。但是必须要了解可以使用什么库函数来实现，代码如下：

class Solution {public:void reverseString(vector<char>& s) {reverse(s.begin(),s.end());}
};

• 时间复杂度：O($n$)。只调用了一次 C++ 标准库中的 reverse 函数，其时间复杂度为 O(n)，其中 n 是数组的大小
• 空间复杂度：O($1$)。没有使用任何额外的内存来存储变量，所以空间复杂度是 O(1)

swap 的两种方式

第一种是比较常见的方式

int tmp = s[i];
s[i] = s[j];
s[j] = tmp;

第二种是通过位运算

int a = 5; // 101
int b = 7; // 111
a ^= b; // 此时 a 的值为 2（101^111=010）
b ^= a; // 此时 b 的值为 5（010^111即(101^111)^111=101)
a ^= b; // 此时 a 的值为 7（010^101即(101^111)^101=111）

解释：利用异或运算符的特性（一个数异或同一个数两次会得到原始的值），这个交换操作不需要临时变量，比第一种方法更快，尤其是在处理大型数据集时。但要注意的是，这种方式只适用于整型数据类型，对于其他类型，例如浮点数、字符或自定义对象等，则需要采用其他方法进行交换。

解题的时候一般的交换元素可以直接用 swap 函数即 swap(a,b)