字符串循环移位的三种算法
字符串操作是面试的一个热点,关于循环移位我总结了了一下,分享给大家。字符串循环移位问题,如题:将一个n位字符串进行循环移位k。例如:对于字符串abcdef循环移位k=2,则输出cdefab。本文给出了三种算法,并且提供了源代码下载
字符串循环移位的三种算法
如题:将一个n位字符串进行循环移位k。例如:对于字符串abcdef循环移位k=2,则输出cdefab。
一、算法一思想:
采用一个辅助空间,将要移动到末尾的k位存储到一个k位的辅助空间,先将n-k个字符往字符串前面移动,然后将辅助空间的k个字符复制到原数组后面。在这里可以采用strncpy函数来简化操作,这个函数是用来拷贝指定地址指定字节的字符串。
二、算法二思想:
直接采用一次交换的思想,即从第i+1个字符开始,将其放置到最终目标位置,当循环结束,所有的字符均到目标位置,达到字符串循环的目的。
三、算法三思想:
从第1到第i个字符倒序,第i+1到第n个倒序,最终所有字符再一次倒序,即可完成字符串循环的目的。
实现代码如下(VC6.0通过测试):
#include <stdio.h>
#include <string>
using namespace std;
//申请辅助空间 空间复杂度为O(n)
void ne(char * str,int i)
{
//将首部i个字符串拷贝到辅助数组
char* temp=new char[i+1];
strncpy(temp,str,i);
temp[i]='\0';
//将第i个字符后面的字符全部前移i个位置
strncpy(str,str+i,strlen(str)-i);
//从辅助空间拷贝i个字符到原字符串尾部
strncpy(str+strlen(str)-i,temp,i);
//释放辅助数组
delete[] temp;
printf("%s\n",str);
}
//字符串循环移位 空间复杂度为O(1)
void re(char * str,int i)
{
//把每个字符置换到目标位置
for(int j=i;j<strlen(str);j++)
{
swap(str[j],str[j-i]);
}
printf("%s\n",str);
}
//字符串倒序
void exchange(char *str,int low,int high)
{
int i=low;
int h=high;
//将字符串倒序采用while循环非常不错!
while(i<h)
{
swap(str[i],str[h]);
i++;
h--;
}
}
//三次倒序算法 空间复杂度为O(1)
void three(char * str,int i)
{
//首部倒序
exchange(str,0,i-1);
//尾部倒序
exchange(str,i,strlen(str)-1);
//整体倒序
exchange(str,0,strlen(str)-1);
printf("%s\n",str);
}
int main()
{
printf("原字符串:abcdef\n");
char name1[]="abcdef";
ne(name1,2);
char name[]="abcdef";
re(name,2);
char test[]="abcdef";
three(test,2);
return 0;
}
输出截图:
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)