0344. Reverse String¶
题目信息¶
- 题号:
0344
- 难度:
Easy
- 主题:
字符数组、原地修改、顺序反转、常数空间
- 原题:
- 重点:
输入是可修改字符数组、函数无返回值、每个字符移动到镜像位置、额外空间必须为 O(1)
题目重述¶
给定字符数组 s,在原数组上把字符顺序完全反转。反转后,原下标 i 的字符应位于下标 s.length-1-i;字符本身不能改变、丢失或重复。
函数通过修改 s 返回结果,不应构造并返回另一个字符串或同长度数组。s 的长度位于 [1, 10^5],每个元素是可打印 ASCII 字符。题目要求只使用 O(1) 额外空间。
自建示例¶
包含大小写和标点:
输入:s = ["C", "o", "d", "e", "!"]
修改后:["!", "e", "d", "o", "C"]
解释:字符按下标顺序整体反转,感叹号从末尾移动到开头。
单字符数组:
输入:s = ["?"]
修改后:["?"]
解释:唯一字符的镜像位置仍是自身。
从两端向中间交换¶
下标 left 与 right = n - 1 - left 互为镜像。只要 left < right,交换这两个位置并让两个指针向中间移动,就能一次确定一对字符的最终位置;指针相遇或交错时,所有位置都已经处理。
C++ 实现¶
class Solution {
public:
void reverseString(std::vector<char>& s) {
int left = 0;
int right = static_cast<int>(s.size()) - 1;
while (left < right) {
std::swap(s[left++], s[right--]);
}
}
};
代码分析¶
每次交换把一对镜像位置放到正确字符,未处理区间严格缩小;单字符或空边界不会进入循环。算法原地完成,时间复杂度为 O(n),额外空间为 O(1)。