现在的位置: 首页 > 综合 > 正文

O(n)时间复杂度旋转字符串

2013年09月13日 ⁄ 综合 ⁄ 共 442字 ⁄ 字号 评论关闭

测试代码如下:

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

//k>0时,向右旋转,k<0时,向左旋转
//返回旋转后的字符串
char * rotate(char * str, int k)
{
    int num, size, start, i;
    char ch, tmp;
    i=0, size=strlen(str), num=0;//忘记初始化num,定义变量时最好初始化
    while(num<size)
    {
        start = i;
        ch = str[i];
        while(1)
        {
            i = i + k;
            if(i<0)i+=size;
            if(i>=size) i%=size;
            if(i==start)break;
            tmp = str[i];
            str[i] = ch;
            ch = tmp;
            ++num;
        }
        str[i] = ch;
        ++num;
        ++i;
    }
    return str;
}

int main()
{
    int k;
    char str[100];
    while(1)
    {
        gets(str);
        scanf("%d", &k);
        getchar();
        puts(rotate(str, k));
    }
}

抱歉!评论已关闭.