/***********************************************************************
目的：实现一个函数，可以左旋字符串中的k个字符。例如：
ABCD左旋一个字符得到BCDA
ABCD左旋两个字符得到CDAB
分析：假设一个字符串里要左旋2次：
▶ 第一种方法（暴力移位法）：
▶ 第二种方法（三步翻转法）：
平台：Visual studio 2017 && windows
*************************************************************************/
📝 实现代码1
#include<stdio.h> #include<assert.h> #include<string.h> void string_left_rotation(char* str, int k) { assert(str); int len = strlen(str); int i = 0; //一次循环左旋一个字符 for(i = 0; i < k; i++) { //拷贝 char temp = *str; //覆盖字符 int j = 0; for(j = 0; j < len - 1; j++) { *(str + j) = *(str + j + 1); } //将拷贝的字符拿上来 *(str + len - 1) = temp; } } int main() { char arr[10] = "ABCDEF"; int k = 2; string_left_rotation(arr, k); printf("%s\n", arr); return 0; }
📝 实现代码2
#include<stdio.h> #include<assert.h> #include<string.h> void reverse(char* left, char* right) { assert(left && right); while(left < right) { char temp = *left; *left = *right; *right = temp; left++; right--; } } void string_left_rotation(char* str, int k) { assert(str); int len = strlen(str); reverse(str, str + k - 1);//第一部分 reverse(str + k, str + len - 1);//第二部分 reverse(str, str + len - 1);//整体 } int main() { char arr[10] = "ABCDEF"; int k = 10; //我们当前写的这个代码是不适用于旋转的字符k大于目标数组的arr，所以如果k大于arr时，我们需要看看k有几个arr,并把它排除掉 k %= strlen(arr); string_left_rotation(arr, k); printf("%s\n", arr); return 0; }
🧿抛砖引玉
/***********************************************************************
目的：写一个函数判断一个字符串是否为另外一个字符串旋转(左旋或右旋)之后的字符串。例如：
1、 S1 = AABCD 和 S2 = BCDAA，返回1
2、 S1 = abcd和 S2 = ABCD，返回0
分析：
▶ 第一种方法：
只要每左旋一次字符串并比较两字符串是否相等即可
▶ 第二种方法（库函数yyds）：
我们发现字符串追加自己后，可以找到所以旋转后的可能性
平台：Visual studio 2017 && windows
*************************************************************************/
📝 实现代码1
#include<stdio.h> #include<assert.h> #include<string.h> int is_string_rotation1(char* str1, char* str2) { assert(str1 && str2); int len = strlen(str1); int i = 0; //一次循环左旋一个字符 for(i = 0; i < len; i++) { //拷贝 char temp = *str1; //覆盖字符 int j = 0; for(j = 0; j < len - 1; j++) { *(str1 + j) = *(str1 + j + 1); } //将拷贝的字符拿上来 *(str1 + len - 1) = temp; //每次旋转一个字符后比较一次 if(strcmp(str1, str2) == 0) { return 1; } } return 0; } int main() { char arr1[] = "AABCD"; char arr2[] = "BCDAA"; int ret = is_string_rotation1(arr1, arr2); if(1 == ret) { printf("Yes\n"); } else { printf("No\n"); } return 0; }
📝 实现代码2
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<assert.h> #include<string.h> int is_string_rotation2(char* str1, char* str2) { assert(str1 && str2); //str1追加str1(注意字符串自己追加自己时不能用strcat，应为它会将'\0'覆盖掉；而strncat在追加完后会补'\0') int len = strlen(str1); strncat(str1, str1, len); //判断str2是否为str1的子串 char* ret = strstr(str1, str2); return ret != NULL;//同下 /*if(ret == NULL) { return 0; } else { return 1; }*/ } int main() { char arr1[20] = "AABCD"; char arr2[] = "BCDAA"; int ret = is_string_rotation2(arr1, arr2); if(1 == ret) { printf("Yes\n"); } else { printf("No\n"); } return 0; }
❓❔ 代码2其实是有问题的：
str1：A A B C D A A B C D
str2：B C D
Yes
str2一定是str1的子串，但是str1一定不是str2旋转得来的
/***********************************************************************
目的：修改代码2中的bug
分析：我们发现当str2与str1长度不相等时，那么一定不可能是旋转得来的
平台：Visual studio 2017 && windows
*************************************************************************/
📝 修改代码2
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<assert.h> #include<string.h> int is_string_rotation2(char* str1, char* str2) { assert(str1 && str2); //修改处 if(strlen(str1) != strlen(str2)) { return 0; } //str1追加str1(注意字符串自己追加自己时不能用strcat，应为它会将'\0'覆盖掉；而strncat在追加完后会补'\0') int len = strlen(str1); strncat(str1, str1, len); //判断str2是否为str1的子串 char* ret = strstr(str1, str2); return ret != NULL;//同下 /*if(ret == NULL) { return 0; } else { return 1; }*/ } int main() { char arr1[20] = "AABCD"; char arr2[] = "BCDAA"; int ret = is_string_rotation2(arr1, arr2); if(1 == ret) { printf("Yes\n"); } else { printf("No\n"); } return 0; }
