| 字符串的循环移位 | 您所在的位置：网站首页 › 字符串的循环 › 字符串的循环移位 |
字符串的循环移位
|
问题描述: 将一个字符串a像左旋转i个位置。例如，当n=8且i=3时(n为字符串有效长度)，向量abcdefgh旋转为defghabc。要求时间复杂度O(n)，空间复杂度为O(1) 问题求解: 直接将前i个数组复制到一个临时数组，将余下的元素左移，再将临时数组中的i个元素复制到末尾的方法可得正确解，但空间复杂度为O(n)。每次移动一个到末尾，剩余的前移也能得正确解，但时间复杂度为O（n^2）。显然，我们需要新的想法。 解法一： 移动a[0]到临时变量t，然后移动a[i]到a[0],a[2i]到x[i]，依次类推（将a中所有下标对n取模）,直至返回到取x[0]中的元素，此时改为从t取值然后终止过程。 代码如下：
#include
#include
//求最大公约数
int gcd(int i,int j)
{
while(i != j )
{
if(i > j)
i = i - j;
else
j = j - i;
}
return i;
}
void turnleft(char *a,int i,int n)
{
int left = i % n;
if(left == 0)
return ;
int gcdnum = gcd(left,n);
int j,k,t,m;
for(j=0;j= n)
k = k - n;
if(k == j)
break;
a[m] = a[k];
m = k;
}
a[m] = t;
}
}
int main()
{
char a[1024];
int i;
printf("请输入字符串: ");
//fgets(a,1024,stdin);//fgets会将结尾的回车换行符也记录下
scanf("%s",a);
printf("请输入左移位数：");
scanf("%d",&i);
int n = strlen(a);
turnleft(a,i,n);
printf("%s\n",a);
}
解法二： 解法一满足了我们的要求，但看起来仍然没那么直观，有没有更清晰移动的方法呢？ 答案就是有。 首先将字符串a分为两段,要移动的前i位为b，剩余部分为c，则字符串可表示为bc，左移i位的结果其实就是cb，则算法的目的就是将bc转换为cb。首先将b逆序为b'，再将c逆序为c'，最后将(b'c')'整体逆序即得到cb。 代码如下：
#include
#include
//将a中从start到end翻转
void reverse(char *a,int start, int end)
{
int i ,j,temp;
for(i = start,j = end; i < j; i++,j--)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
//a为原数据，i为要左翼的位数，n为总长度
void turnleft(char *a,int i,int n)
{
int left = i % n;
if(left == 0)
return ;
reverse(a,0,left-1);
reverse(a,left,n-1);
reverse(a,0,n-1);
return ;
}
int main()
{
char a[1024];
int i;
printf("请输入字符串: ");
//fgets(a,1024,stdin);//fgets会将结尾的回车换行符也记录下
scanf("%s",a);
printf("请输入左移位数：");
scanf("%d",&i);
int n = strlen(a);
turnleft(a,i,n);
printf("%s\n",a);
}
以上两种算法均可以在O(n),O(1)内完成字符串的循环移位。也许有看观会问，这里说的都是循环左移，那循环又移怎么办呢？ 呵，事实上，循环左移和循环右移本质上是一模一样的，循环右移i位其实就是循环左移n-i位而已。 |
【本文地址】
公司简介
联系我们