C语言--字符串旋转笔试题

C语言–字符串旋转笔试题

---

一、字符串左旋

实现一个函数，可以左旋字符串中的k个字符。

例如：

ABCD左旋一个字符得到BCDA

ABCD左旋两个字符得到CDAB

1.1 思路1

先把第一个元素取出来暂时存放在变量中，后面的整体移动到前面，然后把第一个变量存放在最后的位置，循环往复。

1.2 思路1代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<string.h>
void left_move(char arr[], int k)
{int i = 0;int len = strlen(arr);for (i = 0; i < k; i++){//先保存首元素char tmp = arr[0];//将后面的值放到前面int j = 0;for (j = 0; j < len - 1; j++){arr[j] = arr[j + 1];}//将首元素放到最后arr[len - 1] = tmp;}
}
int main()
{char arr[] = "abcdefg";int k = 2;left_move(arr,k);printf("%s", arr);return 0;
}

1.3 思路2

逆序法：
ABCD
例如我要左旋2个字符，首先先将AB逆序，变成BA，然后再将CD逆序，变成DC，此时就是BADC，然后将整体逆序，变成CDBA

1.4 思路2代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<string.h>
#include<assert.h>
//逆序函数
void reverse(char* left, char* right)
{assert(left);assert(right);while (left < right){char tmp = *left;*left = *right;*right = tmp;left++;right--;}}
void left_move(char arr[], int k)
{int i = 0;int len = strlen(arr);//逆序左边reverse(arr, arr + k - 1);//逆序右边reverse(arr + k, arr + len - 1);//逆序整体reverse(arr, arr + len - 1);
}
int main()
{char arr[] = "abcdefg";int k = 2;left_move(arr,k);printf("%s", arr);return 0;
}

二、字符串旋转结果判断

写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。

例如：给定s1 =AABCD和s2 = BCDAA，返回1

给定s1=abcd和s2=ACBD，返回0.

AABCD左旋一个字符得到ABCDA

AABCD左旋两个字符得到BCDAA

AABCD右旋一个字符得到DAABC

2.1 思路1

依赖于上面写过的旋转函数，将字符串旋转之后看两个字符串是否相同来判断

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<assert.h>void reverse(char* left, char* right)
{assert(left);assert(right);while (left < right){char tmp = *left;*left = *right;*right = tmp;left++;right--;}}
void left_move(char arr[], int k)
{int i = 0;int len = strlen(arr);//逆序左边reverse(arr, arr + k - 1);//逆序右边reverse(arr + k, arr + len - 1);//逆序整体reverse(arr, arr + len - 1);
}
int is_left_move(char arr1[], char arr2[])
{int len1 = strlen(arr1);int len2 = strlen(arr2);if (len1 != len2)//如果两个字符串长度不相同，一定不是旋转得来的{return 0;}int i = 0;for (i = 0; i < len1; i++){left_move(arr1, 1);//每次旋转一个，然后判断是否相等if (strcmp(arr1, arr2) == 0)//如果出现小写字母，在这里就会发现{return 1;}}return 0;
}
int main()
{char arr1[] = "AABCD";char arr2[] = "BCDAA";int ret = is_left_move(arr1, arr2);if (ret == 1){printf("YES\n");}else{printf("NO\n");}return 0;}

2.2 思路2

AABCD 如果在后面再加上一组 AABCD 得出 AABCDAABCD那么就会得到AABCD所有旋转之后的结果，在和另一个字符串比较的时候，只需要判断其是不是AABCDAABCD的字串就可以了，前提还是这两个字符串长度相等的情况下

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>int is_left_move(char arr1[], char arr2[])
{int len1 = strlen(arr1);int len2 = strlen(arr2);if (len1 != len2)//如果两个字符串长度不相同，一定不是旋转得来的{return 0;}strncat(arr1, arr1, len1);//字符串追加函数，len1表示追加的个数if (strstr(arr1, arr2) != NULL)//strstr是在arr1字符串中查找arr2是否存在//如果存在则返回arr2在arr1中第一次出现的地址//如果不存在则返回NULL{return 1;}else{return 0;}}
int main()
{char arr1[20] = "AABCD";char arr2[] = "BCDAA";int ret = is_left_move(arr1, arr2);if (ret == 1){printf("YES\n");}else{printf("NO\n");}return 0;}