定义字符串的左旋转操作,把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符串cdefab,请实现字符串左旋转函数。
要求时间复杂度O(n),空间复杂度O(1).
解法1是将前k个字符串反转,后面的字符串同样反转,再对整个字符串进行一次翻转。
解法2如下
public class Rotate {
public static String rotate(String s, int leftSize) {
char[] chars = s.toCharArray();
int L = 0;
int R = s.length() - 1;
int lpart = leftSize;
int rpart = s.length() - leftSize;
int same = Math.min(lpart, rpart);
int diff = lpart - rpart;
exchange(chars, L, R, same);
while (diff != 0) {
if (diff > 0) {
L = L + same;
lpart = diff;
} else {
R = R - same;
rpart = -diff;
}
same = Math.min(lpart, rpart);
diff = lpart - rpart;
exchange(chars, L, R, same);
}
return String.valueOf(chars);
}
private static void exchange(char[] chars, int L, int R, int size) {
int i = R - size + 1;
char tmp = 0;
while (size-- != 0) {
tmp = chars[L];
chars[L] = chars[i];
chars[i] = tmp;
L++;
i++;
}
}
public static void main(String[] args) {
// String s = "abcdef";
// String rotate = rotate(s, 4);
String s = "abcdefgh";
String rotate = rotate(s, 2);
}
}