【前言】：
今天是力扣打卡第12天！
这道题目不是力扣上面的题目，之所以放到这里，是因为我感觉它很好，可以让我们加深对于递归的理解。
原题：逆置字符串
题目描述：
编写一个函数：reverse_string(char* string)(递归实现)
实现：将参数字符串中的字符反向排列，注意哦，不是逆序打印
要求：不能使用C语言库函数中的字符串操作函数
示例：
//输入：abcdef //输出：fedcba
方法一：非递归解决
代码执行：
#include<stdio.h> //方法一：非递归 //自定义函数实现strlen()的功能 int my_strlen(char* arr) { int len = 0; while (*arr != '\0') { len++; arr++; } return len; } //void reverse_string(char* arr) //{ // //采用双指针的方式 // int left = 0; // int right = my_strlen(arr) - 1; // //left == right 时，翻不翻转都无所谓 // while (left < right) // { // char tmp = arr[left]; // arr[left] = arr[right]; // arr[right] = tmp; // left++; // right--; // } //} //上面实现采用的是数组下标的形式，这里不采用数组下标，采用指针解题 void reverse_string(char* arr) { char* left = arr;//指针left指向数组首元素 char* right = arr + my_strlen(arr) - 1; while (left < right) { char tmp = *left; *left = *right; *right = tmp; left++; right--; } } int main() { char arr[] = "abcdef"; reverse_string(arr); printf("%s\n", arr);//fedcba return 0; }
利用非递归解决本题很简单，这道题目使用递归解决反而增加难度了，所以本题只是让大家对于递归有一个更深的认知。
复杂度分析：
时间复杂度：O(N)
空间复杂度：O(1)
方法二：递归解决
代码执行：
方法二：递归版本 说明：其实像这种逆置问题，用非递归解题是非常方便的，用递归反而复杂了 之所以用递归，是在练习递归的技巧 reverse_string("abcdef") 拆化： f reverse_string("bcde") a 难点：将f和a交换一下，然后再逆序“bcde”，此时e后面放的是a,它根本就不知道什么时候结束,也就没办法将它看做一个字符串了 如何解决呢？ 先把a拿出来，再将f放到原先a的位置，然后将原先g的位置放'\0'，此时“bcde”就是一个字符串了，对其逆序，然后再将a拿上来放到最后 #include<stdio.h> //自定义函数实现strlen()的功能 int my_strlen(char* arr) { int len = 0; while (*arr != '\0') { len++; arr++; } return len; } void reverse_string(char* arr) { //找边界--字符串长度不大于1就不需要逆置了 if (my_strlen(arr) <= 1) { return; } int len = my_strlen(arr); char tmp = *arr;//将a拿出来 *arr = *(arr + len - 1);//将f放到a的位置 *(arr + len - 1) = '\0';//将'\0'放到f的位置 reverse_string(arr + 1);//逆置bcde *(arr + len - 1) = tmp;//最后将a放到最后 } int main() { char arr[] = "abcdef"; reverse_string(arr); printf("%s\n", arr);//fedcba return 0; }
复杂度分析：
时间复杂度：O(N)
空间复杂度：O(N)
上面只分析了第一层递归，实在不理解的小伙伴可以将递归展开图画出来，慢慢去感受本题。
结语
今天是力扣打卡第12天！
这些天都是痛并快乐着，每天都很充实，一起加油。
咱们明天再见！
