描述：
定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。
如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数，要求对长度为n的字符串操作的时间复杂度为O(n)，空间复杂度为O(1)对应的详细分析见：
实现：
下面给出两个可靠的java实现：
package com.jiangdx.algrithmn;import java.util.Arrays;public class RotateShift { /** * 假设原数组序列为abcd1234，要求变换成的数组序列为1234abcd，即循环右移了4位。 * 比较之后，不难看出，其中有两段的顺序是不变的：1234和abcd，可把这两段看成两个整体 * 逆序排列abcd：abcd1234 → dcba1234； * 逆序排列1234：dcba1234 → dcba4321； * 全部逆序： dcba4321 → 1234abcd * * @param s * @param bit */ static void reverseRightShift(String[] s, int bit) { /** bit > length */ int length = s.length; bit %= length; reverse(s, 0, length - bit - 1); reverse(s, length - bit, length - 1); reverse(s, 0, length - 1); } static void reverse(String[] s, int start, int end) { for (; start < end; start++, end--) { String t = s[start]; s[start] = s[end]; s[end] = t; } } /** * 所有序号为 (j+i *m) % n (j为0到gcd(n, m)-1之间的某一整数，i = 0:n-1，m表示左旋转位数，n表示字符串长度)， * 会构成一个循环链（共有gcd(n,m)个，gcd为n、m的最大公约数）， * * 每个循环链上的元素只要移动一个位置即可，最后整个过程总共交换了n次 * （每一次循环链，是交换n/gcd(n,m)次，共有gcd(n,m)个循环链，所以，总共交换n次）。 * example: [a, b, c, d, e, 1, 2, 3，4] 右移3位 * gcd=3, 循环链=[a, d, 2] [b, e, 3] [c, 1, 4] * 循环链循环右移1个位置： [2, a, d] [3, b, e] [4, c, 1] * 结果： [2, 3, 4, a, b, c, d, e, 1] * * @param s * @param m */ static void rotateShift(String[] s, int m) { int length = s.length; int gcd = gcd(m, length); int count = length / gcd; for (int j = gcd - 1; j >= 0; j--) { String last = s[(j + (count - 2 + 1) * m) % length]; int first = 0; for (int i = count - 2; i >= 0; i--) { first = (j + i * m) % length; s[(j + (i + 1) * m) % length] = s[(j + i * m) % length]; } s[first] = last; } } /** * 求最大公约数: 1、[求余数]，令r=m%n，r为n除m所得余数（0<=r 0) * @param n * (n > 0) */ static int gcd(int m, int n) { if (m < n) { int t = n; n = m; m = t; } int r = m % n; if (r == 0) return n; /** recursively find it */ m = n; n = r; return gcd(m, n); } public static void main(String[] args) { String[] s = { "a", "b", "c", "d", "1", "2", "3", "4", "32" }; System.err.println(Arrays.toString(s)); // reverseRightShift(s, 5); rotateShift(s, 5); System.out.println(Arrays.toString(s)); }}