剑指offer 左旋转字符串

点击进入 牛客网题库：左旋转字符串

题目描述

汇编语言中有一种移位指令叫做循环左移（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

2. 反转后面的 def -> fed
   就得到字符串 cbafed
3. 整个字符串进行反转 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;
        }
    }
}