学步园

字符串循环移位一直是字符串操作的常见问题，最直观的解决方法是每次将字符串中的元素移动一位，循环k次。这个算法虽然可以实现字符串的循环移位，但是算法的时间复杂度为O(k*n)，其中n为字符串的长度，k为循环移位的位数。为了降低时间复杂度，通过对移位过程的详细分析发现，可以利用中间变量tmp保存str[0, k - 1]，再将str[n - k, n - 1]依次放入str[0, k - 1]，最后将tmp[0, k - 1]依次放入str[k, n
- 1]。

#include <cstdio>
#include <cstdlib>
#include <cstring>

/**********************************************
 * 将给定的字符串str循环右移k位
 **********************************************/
void LoopMove(char *str, int k)
{
	int i, j;
	int n = strlen(str); //字符串中字符个数
	k = k % n;   //移动步数小于字符个数n

	//中间变量tmp保存str[0...k-1]
	char *tmp = (char *)malloc(sizeof(char) * k);
	for(i = 0; i < k; i++)
	{
		tmp[i] = str[i];
	}

	j = 0;
	//将str[n-k...n-1]插入正确位置
	while(i < n)
	{
		str[j++] = str[i++];
	}
	//将tmp[0...k-1]插入正确位置
	for(i = 0; i < k; i++)
	{
		str[j++] = tmp[i];
	}
}

int main()
{
	int n;
	char str[100];
	scanf("%s", str);
	scanf("%d", &n);
	LoopMove(str, n);
	printf("%s\n", str);

	return 0;
}

上述算法的时间复杂度虽然是O(n)，但是在空间上造成了很大的浪费（因为需要申请大小为k % n的字符数组保存中间过程）。

对于字符串s右移k位后得到的s'，比较两个字符串发现：s[0, n - k - 1]与s'[k, n - 1]顺序一致，s[n - k, n - 1]与s'[0, k - 1]顺序一致。

例如s：abcdefgh循环右移3位后得到s'：fghabcde。s[0, 4] = s'[3, 7]，s[5, 7] = s'[0, 2]。

由此我们可以对上述方法进行改进：将字符串s分为两部分s[0, n - k - 1]和s[n - k, n - 1]。右移k位的过程就是将划分的两段分别进行逆序，再对整个字符串进行逆序。

对于abcdefgh右移3位的步骤如下：

1、逆序abcde：abcdefgh -> edcbafgh

2、逆序fgh：edcbafgh -> edcbahgf

3、全部逆序：edcbahgf -> fghabcde

同理我们可以得到循环左移k位的实现方法。而且由以上分析我们也不难写出字符串左（右）移k位的实现代码。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 反转字符串str的l~h位 */
void reverse(char *str, int l, int h)
{
	char c;
	while(l < h)
	{
		c = str[l];
		str[l] = str[h];
		str[h] = c;
		l++; h--;
	}
}

/* 循环右移k位 */
void rightreverse(char *str, int n, int k)
{
	k %= n;
	reverse(str, 0, n - k - 1);
	reverse(str, n - k, n - 1);
	reverse(str, 0, n - 1);
}

/* 循环左移k位 */
void leftreverse(char *str, int n, int k)
{
	k %= n;
	reverse(str, 0, k - 1);
	reverse(str, k, n - 1);
	reverse(str, 0, n - 1);
}

int main()
{
	int k;
	char str[10];
	scanf("%s %d", str, &k);
	rightreverse(str, strlen(str), k);
	printf("right reverse: %s\n", str);
	scanf("%s %d", str, &k);
	leftreverse(str, strlen(str), k);
	printf("left reverse: %s\n", str);

	return 0;
}

上述算法时间复杂度为O(n)，空间复杂为O(1)。实现在线性时间内实现移位操作的同时保证空间复杂度最低。