定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部,如把字符串abcdefghijk左旋转3位得到字符串defghijkabc。要求对长度为n的字符串操作的时间复杂度为O(n),空间复杂度为O(1),文章思路来自:http://blog.csdn.net/v_july_v/article/details/6543438
思路:
1、对于字符串abc def ghi gk,
将abc右移到def ghi gk后面,此时n = 11,m = 3,m’ = n % m = 2;
abc def ghi gk -> def ghi abc gk
2、问题变成gk左移到abc前面,此时n = m’ + m = 5,m = 2,m’ = n % m 1;
abc gk -> a gk bc
3、问题变成a右移到gk后面,此时n = m’ + m = 3,m = 1,m’ = n % m = 0;
a gk bc-> gk a bc。 由于此刻,n % m = 0,满足结束条件,返回结果。
即从左至右,后从右至左,再从左至右,如此反反复复,直到满足条件,返回退出。
代码:
//左旋转字符串 #include <iostream> #include <assert.h> using namespace std; void reverse(string &str,bool flag,int m,int beg,int end,int legth) { assert(&str!=nullptr); if (beg==end||m<0) { return; } if (flag==true) { int p1=beg;//起始点 int p2=beg+m;//要旋转的第一点 int k=legth-m-legth%m;//为每次需要交换操作移动的次数 while (k) { swap(str[p1],str[p2]); p1++; p2++; k--; } k=legth-m-legth%m;//k变为0后重新赋值 reverse(str,false,legth%m,p1,end,legth-k);//重新设置调用函数的起点和终点以及需要处理的字符串长度 } else { int p1=end-m; int p2=end; int k=legth-m-legth%m; while(k) { swap(str[p1],str[p2]); p2--; p1--; k--; } k=legth-m-legth%m; reverse(str,true,legth%m,p1,p2,legth-k); } } int main() { string str="abcdefghijk"; reverse(str,true,3,0,10,11);//左旋转3个 cout<<str.c_str()<<endl; return 0; }