前言
字符串旋转问题：假如给定一个字符串ABCDEF,将他进行左旋操作，例如左旋两个字符便得到EFABCD。右旋两个字符得到CDEFAB。由于字符串左旋和右旋相似，这里便对左旋问题进行叙述，右旋问题给出解决方法
字符串旋转问题的两种解决方法
1.暴力位移法
基本思路：假设我们需要旋转最左边这一个字符a，那么先将a保存在一个临时变量中，然后将整个字符串中的元素向前位移一位进行替换，最后将a放在字符串最后面，则得到②中所示情况。如果移动多位则方法相同，我们只需要通过循环实现就好了.
具体代码实现(此处包含了一个strlen的模拟实现，直接用库函数strlen也可以)：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
36
37
38
39
40
41
int my_strlen(const char *p)
{
assert(p);
int count = 0;
while (*p)
{
p++;
count++;
}
return count;
}
void move_left(char *arr, int count)
{
int len =my_strlen(arr);
assert(arr);
while (count--)
{
int i = 0;
char temp = *arr; //用临时变量temp保存字符串首元素
for (i = 0; i < len - 1; i++)
{
*(arr + i) = *(arr + 1 + i); //各元素依次向前替换
}
*(arr + len - 1) = temp; //将目标旋转字符放入末尾
}
}
int main()
{
char arr[] = "abcdef";
move_left(arr, 3); //正确旋转结果为 defabc
printf("%s\n", arr);
system("pause");
return 0;
}
2.三步反转法
基本思路：我们发现将需旋转的字符部分先进行反转，在将剩余部分字符进行反转，最后将整体进行反转也能的到目标的字符串,如图：
具体代码实现：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
36
37
38
39
40
41
42
43
44
45
46
47
48
int my_strlen(const char *p)
{
assert(p);
int count = 0;
while (*p)
{
p++;
count++;
}
return count;
}
void reverst(char *left, char* right) //反转函数
{
assert(left && right);
while (left<right)
{
char tmp = *left;
*left = *right;
*right = tmp;
left++;
right--;
}
}
void move_left(char *arr, int count)
{
int len = my_strlen(arr);
assert(arr);
reverst(arr,arr+count-1);
reverst(arr+count,arr+len-1);
reverst(arr,arr+len-1);
}
int main()
{
char arr[] = "abcdef";
move_left(arr, 3);
printf("%s\n", arr);
system("pause");
return 0;
}
以上便是左旋字符串问题的解决方法。右旋字符串和左旋字符串相似，在解决时要注意用指针找准各元素的位置
右旋字符串的解决方法
1.暴力位移法
1 |
|
2.三步反转法
1 |
|