剑指offer最优解Java版-左旋转字符串
2019-07-05 本文已影响2人
全菜工程师小辉
题目描述
汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S,请你把其循环左移K位后的序列输出。例如,字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果,即“XYZdefabc”。是不是很简单?OK,搞定它!
解决方法
如果只是使用选取子字符串进行拼接的话,就是去了面试题的意义,所以可以采用下面的方法。
public class Solution {
/**
* 将范围内的字符串进行翻转,闭区间
*/
String fun(char[] chars, int start, int end) {
char temp;
while (start < end) {
temp = chars[start];
chars[start] = chars[end];
chars[end] = temp;
start++;
end--;
}
return new String(chars);
}
public String LeftRotateString(String str, int n) {
int len = str.length();
if (0 == len || 0 == n)
return str;
char[] chars = str.toCharArray();
fun(chars, 0, n - 1);
fun(chars, n, len - 1);
return fun(chars, 0, len - 1);
}
}
复杂度分析:
- 时间复杂度:O(n)。
- 空间复杂度:O(n)。