c - 递归翻转数组

Question

LeetCode 上存在这个问题，我无法在 C/C++ 中工作
这个想法是使用递归在其位置反转数组(不使用其他附加数组)。
链接是:https://leetcode.com/explore/learn/card/recursion-i/250/principle-of-recursion/1440/
该解决方案是用 Java 或 Python 完成的。
我尝试用 C 实现该解决方案，但我总是得到原始数组，我的代码如下:

void reverseString(char* s, int sSize){
    if(!s)
        return;
    reverseString(s+1,sSize-1);
    s[sSize] = *s;
}

有些事情我没有考虑到。请告诉我你将如何解决这个问题，如果可能的话，为什么这不起作用。谢谢。

Answer 1

我会尝试一下。

递归解决方案的一般思想是每次调用都获取一个指向字符串开头的指针，以及要查看的字符数，然后它会一直走到字符串的中间。

void reverseString(char *start, int n)
{
    if (n <= 1) return;

    char tmp = start[0];
    start[0] = start[--n];   // the nth character is start[n-1]
    start[n] = tmp;

    reverseString(++start, --n);
}

在每次递归调用时，起始字符串指针都会增加 1，长度会减少2。

FIRST CALL:   v          v
              hello, world
SECOND CALL:   ^        ^

常见的危险区域是确保它对偶数和奇数长度的字符串执行正确的操作。

这个方法稍微简单一点，只有两个参数，而且 - 正如有些人可能会说的 - 更优雅一点:-)即使 ++ 和 --可能被认为很棘手(一次递增和两次递减)。

编辑:此版本也是 tail recursive ，这可以通过在内部将其转变为循环来实现某些优化。