字符串左旋 与 字符串旋转结果

字符串左旋

实现一个函数，可以左旋字符串中的k个字符。
例如：
ABCD左旋一个字符得到BCDA
ABCD左旋两个字符得到CDAB

方法1

三步翻转法
要求:abcdef 左旋两个

• 整体逆序:fedcba
• 左边逆序:cdef ba
• 右边逆序:cdef ab

#include
#include
#include
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)
{
	assert(arr);
	int len = strlen(arr);
	k %= len;
	reverse(arr, arr + len - 1);//逆序整体
	reverse(arr, arr + len - k - 1);//逆序左边
	reverse(arr + len - k, arr + len - 1);//逆序右边
}
int main()
{
	char arr[] = "abcdef";
	left_move(arr, 2);
	printf("%s\n", arr);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

方法2

• 将第一个元素放到临时变量
• 后面元素前移一位
• 然后把临时变量的值放到最后
• 循环

#include
#include
#include
void left_move(char* arr, int k)
{
	assert(arr);
	size_t len = strlen(arr);
	k %= len;
	while (k--)
	{
		char tmp = *arr;
		size_t i = 0;
		for (i = 0; i < len - 1; i++)
		{
			arr[i] = arr[i + 1];
		}
		arr[len - 1] = tmp;
	}
}
int main()
{
	char arr[] = "abcdef";
	left_move(arr, 2);
	printf("%s\n", arr);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

字符串旋转结果

写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。
例如：
给定s1 =AABCD和s2 = BCDAA，返回1
给定s1=abcd和s2=ACBD，返回0.

AABCD左旋一个字符得到ABCDA

AABCD左旋两个字符得到BCDAA

AABCD右旋一个字符得到DAABC

方法1(穷举)

#include
#include
#include
int is_left_move(char* str1, char* str2)
{
	assert(str1 && str2);
	size_t len1 = strlen(str1);
	size_t len2 = strlen(str2);
	if (len1 != len2)
		return 0;
	int i = 0;
	for (i = 0; i < len1; i++)
	{
		char tmp = *str1;
		size_t j = 0;
		for (j = 0; j < len1 - 1; j++)
		{
			str1[j] = str1[j + 1];
		}
		str1[len1 - 1] = tmp;
		if (!strcmp(str1, str2))
			return 1;
	}
	return 0;
}
int main()
{
	char str1[] = "abcdef";
	char str2[] = "bcdefa";
	if (is_left_move(str1, str2))
		printf("yes");
	else
		printf("no");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

方法2

在原字符串后面追加一个相同的字符串
旋转字符串是这个大的字符串的子字符串

#include
#include
#include
int is_left_move(char* str1, char* str2)
{
	assert(str1&&str2);
	int len1 = strlen(str1);
	int len2 = strlen(str2);
	if (len1 != len2)
		return 0;
	strncat(str1, str1, len1);
	if (strstr(str1, str2) == NULL)
		return 0;
	else
		return 1;
}
int main()
{
	char arr1[30] = "abcdef";
	char arr2[] = "cdefab";
	if (is_left_move(arr1, arr2))
		printf("yes\n");
	else
		printf("no\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26