将一个字符串a像左旋转i个位置。例如,当n=8且i=3时(n为字符串有效长度),向量abcdefgh旋转为defghabc。要求时间复杂度O(n),空间复杂度为O(1)
#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位而已。
相关推荐
首先,让我们来解决字符串循环右移的问题。方法一:利用已有的字符串函数。我们可以使用strcpy函数和strlen函数来实现字符串的循环右移。下面是具体的实现代码: ```c void rightloop(char *a, int n) { char b...
自定义字符串整体循环移位
插入排序、一个英文句子单词逆转,字符串循环移位、去重、全排列算法(递归和非递归实现)、KMP算法
代码如下所示: 代码如下:/************************************************************************//* 给定两个字符串s1和s2,要求判定s2是否能被s1做循环移位得到的字符串所包含例如,给定s1 = AABCD, s2 = ...
本文实例为大家分享了python字符串循环左移的具体代码,供大家参考,具体内容如下 字符串循环左移 给定一个字符串S[0…N-1],要求把S的前k个字符移动到S的尾部,如把字符串“abcdef”前面的2个字符‘a’、‘b’移动...
本篇文章将详细探讨字符串操作相关的知识点,重点讲述字符串循环左移、全排列问题及其解决方案。 首先,字符串循环左移问题是指将一个字符串S的前k个字符移动到字符串的尾部,例如字符串“abcdef”前两个字符“ab”...
1. **字符串循环左移**:这是一个常见的字符串操作,要求将字符串的前k个字符移到末尾。例如,字符串"abcdef"循环左移2位变为"cdefab"。实现这个操作的高效方法是在O(n)的时间复杂度和O(1)的空间复杂度内完成。暴力...
1. **O(n * m)的轮询方法**:这是最直观的解决办法,通过两层循环遍历两个字符串,时间复杂度为O(n * m),其中n是主串长度,m是子串长度。虽然简单,但在数据量较大时效率较低。 ```cpp // 简单示例代码 for (int i...
### 步骤1:检查字符串是否互为对方的循环移位 ```cpp if((str1 + str2) != (str2 + str1)) return ""; ``` 这一步检查 `str1` 是否可以通过将 `str2` 循环移位后与之相等。如果不能,那么它们没有公共因子,返回空...
1. **构造矩阵**:将输入字符串循环移位后形成的字符串集合组成一个 N×N 的矩阵。 2. **排序矩阵**:将矩阵按行进行排序。 3. **获取最后一列**:从排序后的矩阵中提取最后一列作为变换结果的一部分。 **第二步:...
这个项目展示了如何在汇编语言环境下实现字符串的动态显示,以及如何利用位移操作(左移位和右移位)创建动画效果。在实际操作中,汇编语言编程需要对处理器的工作方式有深入理解,包括段寄存器的使用、BIOS 服务...
这个问题可以通过理解字符串移位的性质,结合循环节的概念来解答。计算出现次数需要考虑字符串由多少个完整循环节组成。 5. **拼写检查**:POJ 1035是关于拼写错误检测的,需要在给定的词典中找到可能的正确拼写。...
总结来说,"vc++链表"这个主题涵盖了链表的基本概念、链表的实现、链表操作以及如何在VC++环境中使用链表解决实际问题,如汉诺塔问题和字符串循环移位。理解并熟练掌握这些知识对于进行高效的程序设计和算法实现至关...
标题"**C++ 计算字符串md5_16和md5_32**"指的可能是在C++编程环境中实现计算字符串的MD5值,通常MD5值为32位的十六进制数,但有时为了简洁,可能会只取前16位。这两种形式都是MD5的简化表示,不过16位的形式可能会...
这些运算包括位操作、循环移位、加法和异或等。MD5算法的目的是使得即使只改变输入的一小部分,也会导致输出的散列值发生显著变化,这种特性称为雪崩效应。 32位MD5哈希值是完整的MD5散列结果,它以小写或大写字母...
自己编写的一种简单加密解密算法,通过把多种算法进行组合。特点是同个字符串不同时间加密结果不同,混合了多种加密方式,很难用统计的方式对密文进行破解。 加密过程: ...5)整个字符串循环移位
自己编写的一种简单加密解密算法,通过把多种算法进行组合。特点是同个字符串不同时间加密结果不同,混合了多种加密方式,很难用统计的方式对密文进行破解。 加密过程: 1)扩展字符串 ...5)整个字符串循环移位
ex:输入移动位数 1 输入语句:a 输出 b 输入语句: b 输出 c
1、利用字符串的format函数将int整数值转化为特定位数的二进制值 2、利用字符的切片操作实现循环位移 二、实现代码 # left circular shift #int_value是输入的整数,k是位移的位数,bit是整数对应二进制的位数 def ...