要求:将主串的某一段(n位)翻转到主串的最后,如:abcdef以2位翻转则结果为:cdefab。要求时间复杂度为O(n),空间复杂度为O(1)
思路一:可以重新定义一个与原串相同大小的字符数组result[len],用来存放最终结果,先将原串中的后len-n位复制到result[len]数组的前len-n位,然后将原串的前n位复制到result[len]中的后n位,但这种思路要求重新定义一个中间字符数组用来存放结果。显然空间复杂度不满足要求。
思路二:考虑到句内单词反转这个思路(具体可参看我的博客:句内单词反转),我们可以按位实现三步反转,即对前半部分反转,对后半部分反转,对整体进行反转。基于此思路代码如下:
#include<iostream>
using namespace std;
//该函数实现字符串的反转
void reserve(char *pstr,int start,int end)
{
while(pstr[start]!='\0'&&start<=end)
{
swap(pstr[start],pstr[end]);
start++;
end--;
}
}
//该函数实现字符长的按n位左旋
void left_reserve(char *pstr,int pos)
{
int len=strlen(pstr);
reserve(pstr,0,pos-1);//对前半部分反转
reserve(pstr,pos,len-1);//对后半部分反转
reserve(pstr,0,len-1);//对总体进行反转 }
void main()
{
char str[]={"abcdefg"};
left_reserve(str,2);
cout<<str<<endl;
}
对复杂度分析:反转函数通过一个while循环来扫描主串,时间复杂度为O(n),
用到swap函数空间复杂度为O(1)
程序运行结果如下: