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"]

解题思路

类比和解题步骤

考虑类比：假设你有一串珠子，你希望将其颠倒过来。你可以使用两个指针，一个指向字符串的开头，另一个指向字符串的末尾，然后交换它们指向的字符。

1. 初始化两个指针： 分别指向字符串的开头和末尾。
2. 交换字符： 使用一个循环，不断交换两个指针所指向的字符，然后将指针向中间移动，直到它们相遇。

特殊案例

• 如果输入数组为空，则直接返回空数组。

C#代码实现

public void ReverseString(char[] s) {
    // 如果传入的字符数组为空或者长度小于2，则直接返回
    if (s == null || s.Length < 2) {
        return;
    }

    // 定义左右指针
    int left = 0;
    int right = s.Length - 1;

    // 左指针小于右指针时，交换左右指针指向的字符，并移动指针
    while (left < right) {
        // 交换左右指针指向的字符
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;

        // 移动指针
        left++;
        right--;
    }
}

C代码实现

void reverseString(char* s, int sSize) {
    if (s == NULL || sSize < 2) {
        return;
    }

    int left = 0;
    int right = sSize - 1;

    while (left < right) {
        // 交换左右指针指向的字符
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;

        // 移动指针
        left++;
        right--;
    }
}

时间复杂度和空间复杂度

• 时间复杂度：O(n)，其中 n 是数组 s 的长度。因为我们只遍历了一半的数组。
• 空间复杂度：O(1)。只使用了常数级别的额外空间。