代码之家 › 专栏 › 技术社区 › Sonic Soul

递归字符串反转函数

recursion string c#

Sonic Soul · 技术社区 · 14 年前

    private static char[] ReverseNL(char[] arr, int index)
    {
        var len = arr.Length;
        if (index > 0)
            arr[len - index] ^= arr[index - 1];
        return index-- < 1 ? arr : ReverseNL(arr, index);
    }

“嘿,那是斯塔克!”变成“爱”¨“是的”

更新。。

我想这里不需要异或。。所以用了基本的赋值,也去掉了返回。

    private static void ReverseNL(char[] arr, int index) {
        var len = arr.Length;
        if (index > 0 && index > len / 2) {
            var c = arr[len - index];
            arr[len - index] = arr[index - 1];
            arr[index - 1] = c;
            index--;
            ReverseNL(arr, index);
        }
    }

6 回复 | 直到 14 年前

Marcus Johansson 14 年前

如果需要使用XOR和递归的解决方案,请尝试以下操作:

private static void ReverseNL(char[] arr, int index)
{
    if (index <arr.Length/2)
    {
        arr[index] ^= arr[arr.Length - index-1];
        arr[arr.Length - index-1] ^= arr[index ];
        arr[index] ^= arr[arr.Length - index-1];
        ReverseNL(arr,++index);
    }
}

您不需要返回任何内容,因为所有操作都在数组中完成。当然,您可以删除XOR部分并交换元素,但这是 凉快多了 . ;)

(编辑:索引应从0开始)

strager 14 年前

递归几乎总是用来简化问题。递归算法在本质上也是典型的函数(尽管它们不必是函数)。

在反转字符串(或 char[] ),“simpler”是指“在较小的阵列上操作”。

例如,可以按以下方式减少:

"test"
"est"   't'
"st"    'e'
"t"     's'
""      't'

(左边是数据缩减;右边是切割数据)。

在伪代码中,可以按如下方式执行缩减:

char[] reverse(char[] data) {
    if (data.Count() == 0) {
        return new char[] { };
    }

    char cut = data.First();
    char[] rest = data.Skip(1);

    char [] restReversed = reverse(rest);

    // ???
}

我让你自己来决定下一步需要用你的数据做什么。

Edward Leno 14 年前

    static string ReverseNL (string s)
    {
        if ((s == null) || (s.Length <= 1))
        {
            return s;
        }
        return ReverseNL(s.Substring(1)) + s[0];
    }

    static void Main(string[] args)
    {
        string src = "The quick brown fox";
        Console.WriteLine(src);
        src = ReverseNL(src);
        Console.WriteLine(src);
    }

Henk Holterman 14 年前

一个观察:您正在操作并返回一个数组。总是相同的数组。数组总是一个引用。

这意味着你的回报声明过于复杂和误导。就这样结束吧 return arr; 在所有情况下。

考虑一下一般提示的这一部分:使其更简单,您将更容易看到错误。那个 -- 在return语句中应该单独升起一个危险信号。

// untested, simplified return
private static char[] ReverseNL(char[] arr, int index)
{
    var len = arr.Length;
    if (index > 0)
        arr[len - index] ^= arr[index - 1];

    // return index-- < 1 ? arr : ReverseNL(arr, index);

    if (index >= 1)
         ReverseNL(arr, index-1);

    return arr;     
}

Matthew Abbott 14 年前

在这个特殊的例子中,我宁愿这样做:

return arr.Reverse();

TechNeilogy 14 年前

必须调用XOR两次才能交换一对元素。它只在数组的前半部分被调用一次(在edit中:严格地说,每次赋值只调用一次,因此净效果就像对一半数组执行两个异或交换。)