字符串逆序，面试常考点，由于实现思路很容易，面试官也通常会让你使用多种解法实现，并手写c伪代码，其中每种解法的时空复杂度都要很清楚，能够分析，尤其是最后一种递归实现属于比较进阶的思维了，这种时候最好能讲清楚其中的原理，不过我理解的也不够，这个题也是我面试时遇到的，记录一下。
双指针解法
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define size 5
void reverseString(char* s)
{int i,j;char temp;int length = strlen(s);for (i = 0,j = length-1;i < j;i++,j--){temp = s[i];s[i] = s[j];s[j] = temp;}
}int main()
{char *s;s = malloc(size * sizeof(char));scanf("%s",s);printf("O:%s\n",s);reverseString(s);printf("R:%s\n",s);free(s);
}
复杂度分析：双指针解法的时间复杂度为O(n/2);空间复杂度为O(n);
双字符串解法
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define size 5
void reverseString(char* s,char* s1)
{int i,j;int length = strlen(s);for (i = 0,j = length-1;i < length;i++,j--){s1[i] = s[j];}
}int main()
{char *s;char *s1;s = malloc(size * sizeof(char));s1 = malloc(size * sizeof(char));scanf("%s",s);printf("O:%s\n",s);reverseString(s,s1);printf("R:%s\n",s1);free(s);free(s1);
}
复杂度分析：双字符串解法的时间复杂度为O(n);空间复杂度为O(2n);
递归解法
#include <stdio.h>
void reverse_print()
{ char c;if((c = getchar()) != '\n'){reverse_print();printf("%c",c);}else{return;}
} int main(void)
{ reverse_print();
}
这段程序的时间复杂度主要取决于输入字符串的长度，即输入的字符数。
时间复杂度：
- 递归函数
reverse_print：对于每个字符，函数都会被调用一次，直到字符串的末尾。然后，从递归的最深层开始，逐层返回并打印字符。因此，对于 ( n ) 个字符，递归调用的次数是 ( n )，返回打印的次数也是 ( n )。所以总的时间复杂度是 ( O(n) + O(n) = O(2n) )，简化后就是 ( O(n) )。
结论：
整个程序的时间复杂度是 ( O(n) )，其中 ( n ) 是输入字符串的长度。这是因为每个字符都被处理了两次（一次递归调用，一次打印），但这两个操作都是线性的。
空间复杂度：
- 递归调用：递归深度是 ( n )，因此空间复杂度是 ( O(n) )，这是由于递归调用所需的栈空间。
总的来说，这个程序的时间复杂度是 ( O(n) )，空间复杂度也是 ( O(n) )，其中 ( n ) 是输入字符串的长度。