LeetCode 344: 反转字符串

LeetCode 344: 反转字符串 - C语言题解

这道题的目标是反转一个字符数组（字符串）。我们将通过双指针法来实现这一功能。

代码实现

#include <stdio.h>

void reverseString(char* s, int sSize) {
    int left = 0, right = sSize - 1;  // 定义左右指针
    while (left < right) {  // 当左指针小于右指针时
        char temp = s[right];  // 临时保存右指针处的字符
        s[right--] = s[left];  // 将左指针处的字符放到右指针位置，并右指针向左移动
        s[left++] = temp;  // 将临时保存的字符放到左指针位置，并左指针向右移动
    }
}

int main() {
    char s[] = "hello";  // 测试字符串
    int sSize = 5;  // 字符串的长度
    reverseString(s, sSize);  // 调用反转函数

    printf("Reversed string: %s\n", s);  // 输出反转后的字符串
    return 0;
}

代码解析

1. 函数声明：

   void reverseString(char* s, int sSize)
   

   这个函数接受两个参数：

   • s：字符数组（字符串）。
   • sSize：字符数组的长度。

2. 初始化左右指针：

   int left = 0, right = sSize - 1;
   

   我们使用两个指针left和right来标记字符串的左右端，初始时left指向字符串的第一个字符，right指向字符串的最后一个字符。

3. 循环反转字符：

   while (left < right)
   

   这个while循环会继续进行，直到left大于或等于right为止，即两指针交汇时停止。每次循环中，我们会交换left和right位置的字符。

4. 交换字符：

   char temp = s[right];  // 临时保存右指针处的字符
   s[right--] = s[left];   // 将左指针处的字符放到右指针位置，并右指针向左移动
   s[left++] = temp;       // 将临时保存的字符放到左指针位置，并左指针向右移动
   

   • 我们首先将right位置的字符保存在一个临时变量temp中。
   • 然后将left位置的字符赋给right位置，同时右指针向左移动（right--）。
   • 最后将temp中的字符赋给left位置，同时左指针向右移动（left++）。

5. 主函数：

   int main() {
       char s[] = "hello";
       int sSize = 5;
       reverseString(s, sSize);
       printf("Reversed string: %s\n", s);
       return 0;
   }
   

   在main函数中，我们定义了一个字符数组s，并指定其长度sSize为5。然后调用reverseString函数反转字符串，最后输出反转后的结果。

复杂度分析

• 时间复杂度：$O(n)$，其中$n$是字符串的长度。我们只需要一次遍历来交换字符。
• 空间复杂度：$O(1)$，我们只使用了常数空间来保存临时字符。