Leetcode 344.反转字符串（画图分析）
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
解题思路：
对于长度为 N 的待被反转的字符数组，我们可以观察反转前后下标的变化，假设反转前字符数组为 s[0] s[1] s[2] ... s[N - 1]，那么反转后字符数组为 s[N - 1] s[N - 2] ... s[0]。比较反转前后下标变化很容易得出 s[i] 的字符与 s[N - 1 - i] 的字符发生了交换的规律，因此我们可以得出如下双指针的解法：
将 left 指向字符数组首元素，right 指向字符数组尾元素。
当 left < right：
交换 s[left] 和 s[right]；
left 指针右移一位，即 left = left + 1；
right 指针左移一位，即 right = right - 1。
当 left >= right，反转结束，返回字符数组即可。
这道题目还是比较简单的，不理解的可以看下面的图解和代码，相信看完一定会掌握！
代码实现：
java
class Solution {
public void reverseString(char[] s) {
// 如果字符串为空或长度为0，则直接返回
if (s == null || s.length == 0) {
return;
}
// 左指针从字符串开头开始
int left = 0;
// 右指针从字符串末尾开始
int right = s.length - 1;
// 当左指针小于等于右指针时进行交换
while (left <= right) {
// 暂存右指针处的字符
char temp = s[right];
// 将左指针处的字符赋给右指针
s[right] = s[left];
// 将暂存的字符赋给左指针
s[left] = temp;
// 左指针向右移动
left++;
// 右指针向左移动
right--;
}
}
}
python3
class Solution:
def reverseString(self, s: list) -> None:
# 如果字符串为空或长度为0，则直接返回
if not s or len(s) == 0:
return
# 左指针从字符串开头开始
left = 0
# 右指针从字符串末尾开始
right = len(s) - 1
# 当左指针小于等于右指针时进行交换
while left <= right:
# 交换左右指针处的字符
s[left], s[right] = s[right], s[left]
# 左指针向右移动
left += 1
# 右指针向左移动
right -= 1
c++
class Solution {
public:
void reverseString(vector<char>& s) {
// 如果字符串为空或长度为0，则直接返回
if (s.empty()) {
return;
}
// 左指针从字符串开头开始
int left = 0;
// 右指针从字符串末尾开始
int right = s.size() - 1;
// 当左指针小于等于右指针时进行交换
while (left <= right) {
// 暂存右指针处的字符
char temp = s[right];
// 将左指针处的字符赋给右指针
s[right] = s[left];
// 将暂存的字符赋给左指针
s[left] = temp;
// 左指针向右移动
left++;
// 右指针向左移动
right--;
}
}
};
时间复杂度分析
该算法的核心部分是一个 while 循环，通过两个指针 left 和 right 从数组的两端向中间移动，每次交换数组的两个元素。下面具体分析：
循环条件为 while (left <= right)，其中 left 和 right 分别从数组的两端开始向中间移动。在每次迭代中，两个元素会被交换位置，这需要常数时间 O(1)，且左右指针各向中间移动一次，最多执行 n/2 次循环，其中 n 是数组的长度。
因此，循环的时间复杂度为 O(n)，其中 n 是输入数组的长度。
总的时间复杂度为 O(n)。
空间复杂度分析
- 输入：输入的字符数组是通过引用传递的，算法不需要额外分配与输入大小相关的存储空间。
- 辅助空间：只使用了两个额外的指针变量
left和right，以及一个临时变量temp来交换字符。这些变量的空间占用是常数级别的，即O(1)。
总的空间复杂度为 O(1)。
总结
- 时间复杂度：
O(n)，其中n是字符数组的长度。 - 空间复杂度：
O(1)，因为只使用了常数级别的额外空间。
评论区