c - 递归地反转字符串

Question

好吧，我写了这个程序的 2 个版本。但我正在寻找最好的解决方案 - 最简单、最快速的解决方案。

这是我的解决方案，但我被告知这个解决方案速度较慢 O(n*n)，我不知道真正的含义。我还被告知我可以通过将其分成 2 个功能来固定它，有人可以帮助我这样做吗？

void reverse3(char s[])
{
     int l;
     int i;

     l = strlen(s);
     if(l > 1)
     {
          reverse3(s + 1);

          for(i = 1; i < l; i++)
          {
              int temp = s[i-1];
              s[i-1] = s[i];
              s[i] = temp;
          }
     }
}

Answer 1

你应该交换最外面的字节，即i=1和j=(l-1)，然后i=2，j=(l-2)，等等，直到i <= (j-1)(在换句话说，直到 i=j(对于偶数个字符)或 i=j-1(对于奇数个字符)。

这将在 O(n) 内执行。

递归是不必要的，恕我直言，“将其分成两个函数”似乎也没有必要。

好的，请阅读您对此所做的编辑，这是作业的一部分。

在这种情况下，您确实需要两个函数，正如吉米所说，保存“主”函数的参数列表。

第二个函数类似于:

void swapRecursive(char[s], i, l) {      
   if(i >= (l-1) { return; } // no more swapping needed
   char t = s[i];
   s[i] = (l-i);
   s[l-i] = t;
   swapRecurse(s, i+1, l);
   }

请原谅我生疏的 C，我现在使用的是 C#、VB.NET 和 JavaScript，有些细节我记不清了。

此外，我可能会或可能不会留下错误，因为这是作业。 ;)