本文共 3459 字，大约阅读时间需要 11 分钟。
题目描述：
定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部，如把字符串abcdef左旋转2位得到字符串cdefab。
请实现字符串左旋转的函数，要求对长度为n的字符串操作的时间复杂度为O(n)，空间复杂度为O(1)。
#include#include #include #include #include using namespace std;//第一种方法，官方提供，代码比较简单template void _rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last){ auto next = middle; while (first!=next) { swap (*first++,*next++); if (next==last) next=middle; else if (first==middle) middle=next; }}//第二种方法，递归思路,网友Bluesmic提供的思路 void rotate(string &str, int n, int m, int head, int tail, bool flag) { //n 待处理部分的字符串长度，m：待处理部分的旋转长度 //head：待处理部分的头指针，tail：待处理部分的尾指针 //flag = true进行左旋，flag = false进行右旋 // 返回条件 if (head == tail || m <= 0) return; if (flag == true) { int p1 = head; int p2 = head + m; //初始化p1，p2 //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 //（相信，经过上文中那么多繁杂的叙述，此类的转换过程，你应该是了如指掌了。） int k = (n - m) - n % m; //p1，p2移动距离，向右移六步 /*--------------------- 解释下上面的k = (n - m) - n % m的由来： yansha： 以p2为移动的参照系： n-m 是开始时p2到末尾的长度，n%m是尾巴长度 (n-m)-n%m就是p2移动的距离 比如 abc def efg hi 开始时p2->d,那么n-m 为def efg hi的长度8， n%m 为尾巴hi的长度2， 因为我知道abc要移动到hi的前面，所以移动长度是 (n-m)-n%m = 8-2 = 6。 */ for (int i = 0; i < k; i++, p1++, p2++) swap(str[p1], str[p2]); rotate(str, n - k, n % m, p1, tail, false); //flag标志变为false，结束左旋，下面，进入右旋 } else { //2、右旋：问题变成gk左移到abc前面，此时n = m’ + m = 5，m = 2，m’ = n % m 1; //abc gk -> a gk bc int p1 = tail; int p2 = tail - m; // p1，p2移动距离，向左移俩步 int k = (n - m) - n % m; for (int i = 0; i < k; i++, p1--, p2--) swap(str[p1], str[p2]); rotate(str, n - k, n % m, head, p1, true); //再次进入上面的左旋部分， //3、左旋：问题变成a右移到gk后面，此时n = m’ + m = 3，m = 1，m’ = n % m = 0; //a gk bc-> gk a bc。 由于此刻，n % m = 0，满足结束条件，返回结果。 } } //第三种思路：循环移位法//④ 所有序号为 (j+i *m) % n (j 表示每个循环链起始位置，i 为计数变量，m表示左旋转位数，n表示字符串长度)， //会构成一个循环链（共有gcd(n,m)个，gcd为n、m的最大公约数）， //每个循环链上的元素只要移动一个位置即可，最后整个过程总共交换了n次 //（每一次循环链，是交换n/gcd(n,m)次，共有gcd(n,m)个循环链，所以，总共交换n次）。 int gcd(int a,int b){ return 0==b?a:gcd(b,a%b);}void rotate(string &str, int m) { int lenOfStr = str.length(); int numOfGroup = gcd(lenOfStr, m); int elemInSub = lenOfStr / numOfGroup; for(int j = 0; j < numOfGroup; j++) //对应上面的文字描述，外循环次数j为循环链的个数，即gcd(n, m)个循环链 { char tmp = str[j]; int i; for (i = 0; i < elemInSub - 1; i++) //内循环次数i为，每个循环链上的元素个数，n/gcd(m,n)次 str[(j + i * m) % lenOfStr] = str[(j + (i + 1) * m) % lenOfStr]; str[(j + i * m) % lenOfStr] = tmp; } } //对上述方案4的改写。 //④ 所有序号为 (i+t*k) % n (i为指定整数，t为任意整数)，.... //copyright@ hplonline && July 2011.04.18。 //July、sahala、yansha，updated，2011.06.02。 void my_rotate(char *begin, char *mid, char *end) { int n = end - begin; int k = mid - begin; int d = gcd(n, k); int i, j; for (i = 0; i < d; i ++) { int tmp = begin[i]; int last = i; //i+k为i右移k的位置，%n是当i+k>n时从左重新开始。 for (j = (i + k) % n; j != i; j = (j + k) % n) //多谢laocpp指正。 { begin[last] = begin[j]; last = j; } begin[last] = tmp; } }//第四种方法：三步翻转法template void __rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last){ reverse(first,middle); reverse(middle,last); reverse(first,last);}int main(){ //freopen("C:\\in.txt","r",stdin); string str="abcdefghijk"; int n=14; _rotate(str.begin(),str.begin()+n%str.size(),str.end());//1 rotate(str, str.length(), n % str.length(), 0, str.length() - 1, true);//2 rotate(str,n);//3 my_rotate(&str[0],&str[n%str.length()],&str[str.length()-1]);//3 __rotate(str.begin(),str.begin()+n%str.size(),str.end());//4 cout< <
转载地址：http://efvvi.baihongyu.com/