当前位置：首页 > news >正文

代码随想录刷题-字符串-反转字符串

news 2025/7/21 20:48:47

文章目录

- 反转字符串
- - 习题
  - 双指针
  - swap 的两种方式

反转字符串

本节对应代码随想录中：代码随想录，讲解视频：字符串基础操作！ | 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）