leetcode344----反转字符串
目录
一、题目介绍
二、解法与代码
2.1 标准库函数法
2.2 双指针法
四、补充：reverse函数
4.1 定义及用法
4.2 示例
4.3 reverse时间复杂度与空间复杂度
4.4 总结
一、题目介绍
题目链接：344. 反转字符串 - 力扣（LeetCode）
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"] 输出：["o","l","l","e","h"]
示例 2：
输入：s = ["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]
二、解法与代码
2.1 标准库函数法
直接使用C++中的标准库函数reverse。
#include<algorithm>
#include<string>
#include<iostream>
int main(){
std::string s="hello";
std::cout<<"反转之前的字符串如下："<<s<<std::endl;
std::reverse(s.begin(),s.end());
std::cout<<"反转之后的字符串如下："<<s;
return 0;
}
// 程序输出：
// 反转之前的字符串如下：hello
// 反转之后的字符串如下：olleh2.2 双指针法
对于字符串，我们定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素。
以字符串hello为例，过程如下：
// 反转字符串
// 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
// 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
#include<string>
#include<iostream>
#include<vector>
#include<algorithm>
void reverseString(std::vector<char>& s){
// 定义双指针，i指向字符数组的开始，j指向字符数组的结尾
int i=0;
int j=s.size()-1;
for(i,j;i<s.size()/2;i++,j--){
std::swap(s[i],s[j]);
}
}
void PrintString(std::vector<char>& s){
for(int i=0;i<s.size();i++){
std::cout<<s[i]<<" ";
}
std::cout<<std::endl;
}
int main(){
//char s[]={'h','e','l','l','o','\0'};
// char s[]="hello";
std::string str = "hello";
std::vector<char> s(str.begin(), str.end()); // 不会包含 '\0'
std::cout<<"反转之前的字符串：";
PrintString(s); // 打印字符串
reverseString(s); // 字符串反转
std::cout<<"反转之后的字符串：";
PrintString(s); // 打印字符串
return 0;
}
- 时间复杂度: O(n)
- 空间复杂度: O(1)
时间复杂度分析
s.size()是O(1)操作，因为std::vector维护了其大小信息。- 循环执行
s.size()/2次：
for(i, j; i < s.size()/2; i++, j--)只遍历s前一半的元素，交换它们与s后一半的对应元素。- 每次迭代进行一次
std::swap(s[i], s[j])，时间复杂度为O(1)。- 总共执行
O(n/2) ≈ O(n)次交换。综上，时间复杂度为：O(n)
空间复杂度分析
- 该算法仅使用了
int i和int j两个变量（占用O(1)的额外空间）。std::swap(s[i], s[j])只是交换元素，没有使用额外的存储空间。std::vector<char>& s是引用传递，不涉及数组的复制。综上，空间复杂度为：O(1)
最终结论
复杂度 分析 时间复杂度 O(n) —— 遍历 n/2次，每次O(1)交换空间复杂度 O(1) —— 仅使用了常数级额外变量 这是一种原地（in-place）双指针反转字符串的高效方法。
四、补充：reverse函数
4.1 定义及用法
在 C++ 中，reverse 是 STL（标准模板库）算法中的一个函数，定义在 <algorithm> 头文件中。它用于反转容器（如 std::vector、std::string、std::array）或 C++ 数组的元素顺序。
void reverse(RandomAccessIterator first, RandomAccessIterator last);
first：指向要反转范围的起始位置（包含）。last：指向要反转范围的结束位置（不包含）。- 作用：反转
[first, last)之间的元素顺序。
4.2 示例
#include <iostream>
#include <algorithm> // 需要包含这个头文件
#include <vector>
#include <string>
int main() {
// 示例 1：反转数组
int arr[] = {1, 2, 3, 4, 5};
std::reverse(arr, arr + 5); // 反转整个数组
for (int num : arr) std::cout << num << " "; // 输出: 5 4 3 2 1
std::cout << std::endl;
// 示例 2：反转 vector
std::vector<int> vec = {10, 20, 30, 40, 50};
std::reverse(vec.begin(), vec.end());
for (int num : vec) std::cout << num << " "; // 输出: 50 40 30 20 10
std::cout << std::endl;
// 示例 3：反转字符串
std::string str = "abcdef";
std::reverse(str.begin(), str.end());
std::cout << str << std::endl; // 输出: fedcba
return 0;
}
1. 反转部分容器
std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8};
std::reverse(vec.begin() + 2, vec.begin() + 6); // 仅反转索引2到5的部分
// 结果: vec = {1, 2, 6, 5, 4, 3, 7, 8}
2. 反转 C++ 数组
int arr[] = {9, 8, 7, 6, 5};
std::reverse(arr, arr + 5); // 反转整个数组
// arr 变为: {5, 6, 7, 8, 9}
3. 反转 C++ 字符串
std::string s = "hello";
std::reverse(s.begin(), s.end()); // 反转整个字符串
// s 变为: "olleh"
4.3 reverse时间复杂度与空间复杂度
- 时间复杂度：
O(n) - 空间复杂度：
O(1)（原地反转，不使用额外空间）
reverse函数的时间复杂度是 O(n)，这是因为它需要遍历给定范围的元素并逐个交换位置，直到整个范围被反转。分析过程：
假设我们要反转一个有
n个元素的容器（例如一个数组或向量），范围是从first到last，即[first, last)。reverse的工作过程如下：
交换元素：
reverse会首先交换范围的第一个元素与最后一个元素。- 然后交换第二个元素与倒数第二个元素。
- 依此类推，直到交换到中间位置。
总的交换次数：
- 对于
n个元素，最多需要交换n/2次。- 每次交换操作的时间复杂度是 O(1)（常数时间）。
总结：
- 每个元素最多交换一次，所以交换操作的总次数是 n/2，即 O(n)。
- 因此，
reverse的时间复杂度为 O(n)。
直观理解：
reverse函数本质上是通过两端逐步交换元素，直到整个序列反转。无论是反转数组、字符串还是其他容器，操作的时间复杂度始终与容器中的元素数量成正比，因此为 O(n)。
4.4 总结
✅ reverse 可用于数组、std::vector、std::string 等可随机访问的容器。
✅ 反转的范围是 [first, last)，last 不包含。
✅ 其时间复杂度为 O(n)，且是原地算法（不会额外占用内存）。
------------------------------------------------------声明--------------------------------------------------------------------
参考文章：代码随想录
本篇博文仅用于自主学习用途！！