字符串逆序

字符串逆序，面试常考点，由于实现思路很容易，面试官也通常会让你使用多种解法实现，并手写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) )。