当前位置:首页 » 数据结构精品文章 » 正文

数据结构经典面试题:多种方法实现字符串循环移位

1009 人参与  2018年08月18日 09:01  分类 : 数据结构精品文章  评论

image.png

问题描述:

    要求在时间复杂度和空间复杂度分别为O(n)和O(1)的条件下把一个长度为N的字符串循环左移M位,例如将长度为9的字符串"123456789"循环左移4位后得到字符串"567891234"。程序的输入为N(字符串长度)和M(循环左移的位数),输出为循环移位后的字符串。

解题思路:

    乍一看此题,一般人都会这样想:先把字符串的前M个字符复制到临时数组变量中,然后将余下N-M个字符都分别向左移动M位,再把临时数组变量中的M个字符粘到N-M个字符的末尾。是否很简单呢?但是,这种做法的空间复杂度是O(n),不符合要求。

    这样一来,二般人出现了,他们会这样想:每次都把字符串的第一个字符复制到字符串的最后位置,然后再将整个字符串左移一位,就这样重复M次即可得到最终解。这种做法不需要额外存储空间,的确很聪明,但是,其时间复杂度是(n2),也不符合要求。

    而我们,显然是第三般人,比前两般人都聪明,请看如下两种解法:

解法一:

    移动a[0]到临时变量t,然后移动a[i]到a[0],a[2i]到x[i],依次类推(将a中所有下标对n取模),直至返回到取x[0]中的元素,此时改为从t取值然后终止过程。

代码如下:

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

//求最大公约数
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<gcdnum;j++)
     {
        t = a[j];     
         m = j;
         k = m + left;
         while(1)
        {
            k = m + left;
            if(k >= 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);

}

解法二:

    上面的解法比较麻烦,也比较复杂,虽然是满足了要求,但并不那么容易一下子就看懂,既然条条大路通罗马,我们为啥不选择一条最近、最好走的呢?

    先把原始字符串S一分为二,要移动M位的部分是A,余下的部分为B,那么整个字符串就可以用AB来表示,向左移动M位后得到的其实就是BA,则程序的功能就是将AB转换为BA。我们可以先把A逆序得到A',再把B逆序得到B',最后再把(A'B')'逆序就可以得到BA啦,欧耶!好聪明啊! 

代码如下:

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

//把str中从head到tail反转
void fanzhuan(char *str,int head, int tail)
{
    int i ,j,buf;
    for(i = head,j = tail; i < j; i++,j--)
    {
        buf = str[i];
        str[i] = str[j];
        str[j] = buf;
    }
    
}


//str是原数据,m是要左移的位数,n是字符串的总长度
void leftmove(char *str,int m,int n)
{
    int left = m % n;

    if(left == 0)
        return ;

    fanzhuan(str,0,left-1);
    fanzhuan(str,left,n-1);
    fanzhuan(str,0,n-1);
}

void main()
{
    char str[2048];
    int M;
    int len
    
    gets(str);
    scanf("%d",&M);
    len = strlen(str);
    leftmove(str,M,len);
    printf("%s\n",str);
}

    对于以上两种解法,在时间复杂度和空间复杂度方面,都符合题目的要求。如果您还没有看懂,就再多看两遍,如果看懂了,我还要请教您一个问题:如果是循环右移呢?该咋办?呵呵,原来so easy!循环右移M位的实质其实就是循环左移N-M位,仔细想想,对吧?

来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=12

数据结构习题解析  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!