`
akakori
  • 浏览: 12880 次
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

字符串的循环移位

 
阅读更多


问题描述:

  将一个字符串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 <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);

}
复制代码

 

 解法二:

   解法一满足了我们的要求,但看起来仍然没那么直观,有没有更清晰移动的方法呢? 答案就是有。

     首先将字符串a分为两段,要移动的前i位为b,剩余部分为c,则字符串可表示为bc,左移i位的结果其实就是cb,则算法的目的就是将bc转换为cb。首先将b逆序为b',再将c逆序为c',最后将(b'c')'整体逆序即得到cb。 

    代码如下:

 

复制代码
#include <stdio.h>
#include <string.h>

//将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位而已。 

分享到:
评论

相关推荐

    C语言中关于字符串左右循环移位的问题

    首先,让我们来解决字符串循环右移的问题。方法一:利用已有的字符串函数。我们可以使用strcpy函数和strlen函数来实现字符串的循环右移。下面是具体的实现代码: ```c void rightloop(char *a, int n) { char b...

    VB 字符串整体循环移位函数

    自定义字符串整体循环移位

    字符串处理常见算法实现

    插入排序、一个英文句子单词逆转,字符串循环移位、去重、全排列算法(递归和非递归实现)、KMP算法

    基于字符串移位包含的问题详解

    代码如下所示: 代码如下:/************************************************************************//* 给定两个字符串s1和s2,要求判定s2是否能被s1做循环移位得到的字符串所包含例如,给定s1 = AABCD, s2 = ...

    python字符串循环左移

    本文实例为大家分享了python字符串循环左移的具体代码,供大家参考,具体内容如下 字符串循环左移 给定一个字符串S[0…N-1],要求把S的前k个字符移动到S的尾部,如把字符串“abcdef”前面的2个字符‘a’、‘b’移动...

    数据结构和算法:字符串

    本篇文章将详细探讨字符串操作相关的知识点,重点讲述字符串循环左移、全排列问题及其解决方案。 首先,字符串循环左移问题是指将一个字符串S的前k个字符移动到字符串的尾部,例如字符串“abcdef”前两个字符“ab”...

    数据结构-字符串.pptx

    1. **字符串循环左移**:这是一个常见的字符串操作,要求将字符串的前k个字符移到末尾。例如,字符串"abcdef"循环左移2位变为"cdefab"。实现这个操作的高效方法是在O(n)的时间复杂度和O(1)的空间复杂度内完成。暴力...

    关于字符串包含的问题

    1. **O(n * m)的轮询方法**:这是最直观的解决办法,通过两层循环遍历两个字符串,时间复杂度为O(n * m),其中n是主串长度,m是子串长度。虽然简单,但在数据量较大时效率较低。 ```cpp // 简单示例代码 for (int i...

    字符串的最大公因子(substr+辗转相除)1

    ### 步骤1:检查字符串是否互为对方的循环移位 ```cpp if((str1 + str2) != (str2 + str1)) return ""; ``` 这一步检查 `str1` 是否可以通过将 `str2` 循环移位后与之相等。如果不能,那么它们没有公共因子,返回空...

    Burrows-Wheeler Transformation(BWT)压缩算法

    1. **构造矩阵**:将输入字符串循环移位后形成的字符串集合组成一个 N×N 的矩阵。 2. **排序矩阵**:将矩阵按行进行排序。 3. **获取最后一列**:从排序后的矩阵中提取最后一列作为变换结果的一部分。 **第二步:...

    微机原理课程设计之字符串动画显示

    这个项目展示了如何在汇编语言环境下实现字符串的动态显示,以及如何利用位移操作(左移位和右移位)创建动画效果。在实际操作中,汇编语言编程需要对处理器的工作方式有深入理解,包括段寄存器的使用、BIOS 服务...

    其他字符串相关题解1

    这个问题可以通过理解字符串移位的性质,结合循环节的概念来解答。计算出现次数需要考虑字符串由多少个完整循环节组成。 5. **拼写检查**:POJ 1035是关于拼写错误检测的,需要在给定的词典中找到可能的正确拼写。...

    vc++链表

    总结来说,"vc++链表"这个主题涵盖了链表的基本概念、链表的实现、链表操作以及如何在VC++环境中使用链表解决实际问题,如汉诺塔问题和字符串循环移位。理解并熟练掌握这些知识对于进行高效的程序设计和算法实现至关...

    C++ 计算字符串md5_16和md5_32

    标题"**C++ 计算字符串md5_16和md5_32**"指的可能是在C++编程环境中实现计算字符串的MD5值,通常MD5值为32位的十六进制数,但有时为了简洁,可能会只取前16位。这两种形式都是MD5的简化表示,不过16位的形式可能会...

    MD5加密字符串(32位,16位大小写输出)

    这些运算包括位操作、循环移位、加法和异或等。MD5算法的目的是使得即使只改变输入的一小部分,也会导致输出的散列值发生显著变化,这种特性称为雪崩效应。 32位MD5哈希值是完整的MD5散列结果,它以小写或大写字母...

    简单的加密解密算法,混合了多种加密操作

    自己编写的一种简单加密解密算法,通过把多种算法进行组合。特点是同个字符串不同时间加密结果不同,混合了多种加密方式,很难用统计的方式对密文进行破解。 加密过程: ...5)整个字符串循环移位

    简单的加密解密算法,混合多种加密操作

    自己编写的一种简单加密解密算法,通过把多种算法进行组合。特点是同个字符串不同时间加密结果不同,混合了多种加密方式,很难用统计的方式对密文进行破解。 加密过程: 1)扩展字符串 ...5)整个字符串循环移位

    C++ 循环移位简单加密

    ex:输入移动位数 1 输入语句:a 输出 b 输入语句: b 输出 c

    python实现整数的二进制循环移位

    1、利用字符串的format函数将int整数值转化为特定位数的二进制值 2、利用字符的切片操作实现循环位移 二、实现代码 # left circular shift #int_value是输入的整数,k是位移的位数,bit是整数对应二进制的位数 def ...

Global site tag (gtag.js) - Google Analytics