344.反转字符串

LeetCode LeetCode 双指针字符串

发布时间 : 2000-01-10 03:04

字数:1.5k 阅读 :

评论:

344.反转字符串

344.反转字符串

344.1 题目

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

1 <= s.length <= 10^5
s[i] 都是 ASCII 码表中的可打印字符

344.2 题解

双指针法

// 方法一：双指针法
// 使用两个指针，一个从头开始，一个从尾开始，依次交换两个指针指向的元素，直到两指针相遇。
static void ReverseString1(char[] s)
{
    // 初始化左指针为数组的起始位置
    int left = 0;

    // 初始化右指针为数组的末尾位置
    int right = s.Length - 1;

    // 使用循环，直到左指针不再小于右指针
    while (left < right)
    {
        // 临时变量用于暂存左指针位置的元素值
        char temp = s[left];

        // 将右指针位置的元素值赋给左指针位置
        s[left] = s[right];

        // 将临时变量中的元素值赋给右指针位置，实现元素值的交换
        s[right] = temp;

        // 元组解构语法（不在此代码段使用，已注释掉）
        // (s[left], s[right]) = (s[right], s[left]);

        // 移动左指针向右移动一个位置
        left++;

        // 移动右指针向左移动一个位置
        right--;
    }
}

递归法

// 方法二：递归法
// 使用递归来反转字符串，将字符串分为头尾两部分，先反转尾部，再反转头部，最后将整个字符串反转。
static void ReverseString2(char[] s)
{
    // 调用递归辅助函数，反转整个字符数组
    ReverseHelper(s, 0, s.Length - 1);
}

// 递归辅助函数
static void ReverseHelper(char[] s, int left, int right)
{
    // 递归终止条件：当左指针不小于右指针时，表示数组已反转完成
    if (left >= right)
    {
        return;
    }

    // 交换头尾两部分的元素，实现数组的反转
    char temp = s[left];
    s[left] = s[right];
    s[right] = temp;

    // 元组解构语法（不在此代码段使用，已注释掉）
    // (s[left], s[right]) = (s[right], s[left]);

    // 递归调用，反转剩余部分，缩小数组范围
    ReverseHelper(s, left + 1, right - 1);
}

344.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
        // 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

        // 示例 1：
        // 输入：s = ["h","e","l","l","o"]
        // 输出：["o","l","l","e","h"]

        // 示例 2：
        // 输入：s = ["H","a","n","n","a","h"]
        // 输出：["h","a","n","n","a","H"]

        // 提示：
        // 1 <= s.length <= 105
        // s[i] 都是 ASCII 码表中的可打印字符

        #endregion

        #region 测试

        // 示例 1
        char[] str1 = { 'h', 'e', 'l', 'l', 'o' };
        ReverseString1(str1);
        Console.Write("示例1 方法1 输出：");
        PrintCharArray(str1);

        char[] str1_2 = { 'h', 'e', 'l', 'l', 'o' };
        ReverseString2(str1_2);
        Console.Write("示例1 方法2 输出：");
        PrintCharArray(str1_2);

        // 示例 2
        char[] str2 = { 'H', 'a', 'n', 'n', 'a', 'h' };
        ReverseString1(str2);
        Console.Write("示例2 方法1 输出：");
        PrintCharArray(str2);

        char[] str2_2 = { 'H', 'a', 'n', 'n', 'a', 'h' };
        ReverseString2(str2_2);
        Console.Write("示例2 方法2 输出：");
        PrintCharArray(str2_2);

        #endregion
    }

    #region 答案

    // 方法一：双指针法
    // 使用两个指针，一个从头开始，一个从尾开始，依次交换两个指针指向的元素，直到两指针相遇。
    static void ReverseString1(char[] s)
    {
        // 初始化左指针为数组的起始位置
        int left = 0;

        // 初始化右指针为数组的末尾位置
        int right = s.Length - 1;

        // 使用循环，直到左指针不再小于右指针
        while (left < right)
        {
            // 临时变量用于暂存左指针位置的元素值
            char temp = s[left];

            // 将右指针位置的元素值赋给左指针位置
            s[left] = s[right];

            // 将临时变量中的元素值赋给右指针位置，实现元素值的交换
            s[right] = temp;

            // 元组解构语法（不在此代码段使用，已注释掉）
            // (s[left], s[right]) = (s[right], s[left]);

            // 移动左指针向右移动一个位置
            left++;

            // 移动右指针向左移动一个位置
            right--;
        }
    }


    // 方法二：递归法
    // 使用递归来反转字符串，将字符串分为头尾两部分，先反转尾部，再反转头部，最后将整个字符串反转。
    static void ReverseString2(char[] s)
    {
        // 调用递归辅助函数，反转整个字符数组
        ReverseHelper(s, 0, s.Length - 1);
    }

    // 递归辅助函数
    static void ReverseHelper(char[] s, int left, int right)
    {
        // 递归终止条件：当左指针不小于右指针时，表示数组已反转完成
        if (left >= right)
        {
            return;
        }

        // 交换头尾两部分的元素，实现数组的反转
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;

        // 元组解构语法（不在此代码段使用，已注释掉）
        // (s[left], s[right]) = (s[right], s[left]);

        // 递归调用，反转剩余部分，缩小数组范围
        ReverseHelper(s, left + 1, right - 1);
    }

    #endregion

    #region 辅助函数

    // 打印字符数组
    static void PrintCharArray(char[] arr)
    {
        foreach (char c in arr)
        {
            Console.Write($"{c} ");
        }

        Console.WriteLine();
    }

    #endregion
}

344.4 运行结果

示例1 方法1 输出：o l l e h 
示例1 方法2 输出：o l l e h 
示例2 方法1 输出：h a n n a H 
示例2 方法2 输出：h a n n a H

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com