题目描述
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结>果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输>出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
方法一 时间复杂度O(string.length * n)
public class Solution {
public String LeftRotateString(String str,int n) {
if(str == null || "".equals(str)) {
return "";
}
char[] c = str.toCharArray();
while(n-- > 0) {
c = moveStr(c);
}
return new String(c);
}
private char[] moveStr(char[] c) {
char t = c[0];
for(int i = 1; i < c.length; i++) {
c[i-1] = c[i];
}
c[c.length - 1] = t;
return c;
}
}
方法二 时间复杂度 O(n) 空间复杂度 O(1)
假设，输入进来的是 abcdef 我要反转 n= 3
1先反转前面的 abc -> cba
就得到字符串 cbadef
- 反转后面的 def -> fed
就得到字符串 cbafed- 整个字符串进行反转 cbafed -> defabc
这个结果就出来了
public class Solution {
public String LeftRotateString(String str,int n) {
if(str == null || "".equals(str)) {
return "";
}
char[] c = str.toCharArray();
int len = str.length();
n %= len;
//先反转前面的
reverseStr(c, 0, n - 1);
//再反转后面的
reverseStr(c, n, len - 1);
//最后一起反转
reverseStr(c, 0, len - 1);
return new String(c);
}
private void reverseStr(char[] c, int start, int end) {
while(start < end) {
char t = c[start];
c[start++] = c[end];
c[end--] = t;
}
}
}
