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