在力扣或者牛客网这些OJ刷题平台经常能够看到一些题目，要求你将字符串逆置或者旋转字符串、亦或者旋转数组。那今天就跟大家讲解一下逆置算法。首先我们来学习一下逆置字符串。
逆置字符串
循环版本
代码示例：
#include <stdio.h> #include <string.h> void reverse_string(char* arr) { char *left = arr; char *right = arr+strlen(arr)-1; while(left<right) { char tmp = *left; *left = *right; *right = tmp; left++; right--; } } int main() { char arr[] = "joyy"; reverse(arr); printf("%s\n", arr); return 0; }
#include <stdio.h> #include <string.h> void reverse_string(char* arr) { int len = strlen(arr); int i = 0; for (i = 0; i < len / 2; i++) { char temp = *(arr + i); *(arr + i) = *(arr + len - 1 - i); *(arr + len - 1 - i) = temp; } } int main() { char arr[] = "joyy"; reverse_string(arr); printf("%s\n", arr); return 0; }
递归版本
代码示例：
#include <stdio.h> #include <string.h> void reverse_string(char* arr) { int len = strlen(arr); char tmp = *arr; *arr = *(arr+len-1); *(arr+len-1) = '\0'; if(strlen(arr+1)>=2) //判断条件改为strlen(arr+1)>0也行 reverse_string(arr+1); *(arr+len-1) = tmp; } int main() { char arr[] = "joyy"; reverse_string(arr); printf("%s\n", arr); return 0; }
注意：上面循环的两个版本思路差不多，使用while循环的实现方式是通过指针加加减减来实现交换，而for循环的实现方式是通过下标的方式来堆成交换。 然后递归版本最需要注意的点就是：将*(str+len-1)赋给*arr后，一定要将*(str+len-1)改为'\0'以减小字符串的长度，否则无法实现递归。
旋转数组
示例：给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例：
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
暴力求解法
分析：
代码示例：
#include <stdio.h> void rotate(int* nums, int numsSize, int k) { k %= numsSize; for (int i = 0; i < k; i++) { int temp = nums[numsSize - 1]; for (int k = numsSize - 2; k >= 0; k--) { nums[k + 1] = nums[k]; } nums[0] = temp; } } int main() { int arr[] = { 1,2,3,4,5,6,7 }; rotate(arr, 7, 10); for (int i = 0; i < 7; i++) { printf("%d ", arr[i]); } return 0; }
这种方法还是比较容易想到的方法，但是它不是最优的方法。接下来，博主给大家介绍一种更加优的方法。
反转法
分析：
反转法主要涉及了三次逆置：第一次是前n-k个元素逆置，第二次是后k个元素逆置，第三次是整个数组逆置。所以反转法需要借助上面已经介绍到了的逆置算法。
代码示例：
void rotate(int* nums, int numsSize, int k) { k %= numsSize; //前n-k个元素逆置 reverse(nums, 0, numsSize - k - 1); //后k个元素逆置 reverse(nums, numsSize - k, numsSize - 1); //整个数组逆置 reverse(nums, 0, numsSize - 1); } int main() { int arr[] = { 1,2,3,4,5,6,7 }; rotate(arr, 7, 3); for (int i = 0; i < 7; i++) { printf("%d ", arr[i]); } return 0; }
倒置字符串
将一句话的单词进行倒置，标点不倒置。比如 "I like beijing."，经过处理后变为："beijing. like I"。字符串长度不超过100。
输入描述:输入一个仅包含小写字母、空格、'.' 的字符串，长度不超过100。'.' 只出现在最后一个单词的末尾。
输出描述:依次输出倒置之后的字符串，以空格分割。
示例1
输入
I like beijing.
输出
beijing. like I
解题思路：首先进行单词逆序，然后再进行整个字符串的逆序，就能达到题目想要的效果了。因为单词之间有空格隔开，所以我们需要知道空格的位置。
#include <stdio.h> #include <assert.h> #include <string.h> void reverse(char* left, char* right) { assert(left); assert(right); while (left < right) { char tmp = *left; *left = *right; *right = tmp; left++; right--; } } int main() { char arr[101] = { 0 }; gets(arr); //处理 char* cur = arr; //逆序每个单词 while (*cur) { char* start = cur; char* end = cur; while (*end != ' ' && *end != '\0') { end++; } reverse(start, end - 1); //如果*end等于\0，将end+1赋给cur的话，cur将不会指向\0，无法终止循环 if (*end != '\0') cur = end + 1; else cur = end; } //逆序整个字符串 int len = strlen(arr); reverse(arr, arr + len - 1); printf("%s\n", arr); return 0; }
写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。
例如：给定s1 =AABCD和s2 = BCDAA，返回1
给定s1=abcd和s2=ACBD，返回0.
AABCD左旋一个字符得到ABCDA
AABCD左旋两个字符得到BCDAA
AABCD右旋一个字符得到DAABC
#include <stdio.h> #include <string.h> #include <assert.h> int is_left_move(char* arr1, char* arr2) { assert(arr1 && arr2); int len = strlen(arr1); int i = 0; for (i = 0; i < len; i++) { char tmp = arr1[0]; int j = 0; for (j = 0; j < len - 1; j++) { arr1[j] = arr1[j + 1]; } arr1[len - 1] = tmp; if (strcmp(arr1, arr2) == 0) { return 1; } } return 0; } int main() { char arr1[] = "ABCDEF"; char arr2[] = "CDEFAB"; int ret = is_left_move(arr1, arr2); if (ret == 1) { printf("Yes\n"); } else { printf("No\n"); } return 0; }
#include <stdio.h> #include <string.h> #include <assert.h> int is_left_move(char* arr1, char* arr2) { assert(arr1 && arr2); int len1 = strlen(arr1); int len2 = strlen(arr2); if (len1 != len2) { return 0; } strncat(arr1, arr1, len1); char* ret = strstr(arr1, arr2); if (ret == NULL) { return 0; } else { return 1; } } int main() { char arr1[20] = "ABCDEF"; char arr2[] = "CDEFAB"; int ret = is_left_move(arr1, arr2); if (ret == 1) { printf("Yes\n"); } else { printf("No\n"); } return 0; }
总结：左旋是首先前k个逆序，然后后n-k个逆序，最后整体逆序；右旋是首先前n-k个逆序，然后后k个逆序，最后整体逆序以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以给个三连支持一下！谢谢大家啦！
结语
每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根。
