點(diǎn)擊進(jìn)入 牛客網(wǎng)題庫(kù)：左旋轉(zhuǎn)字符串

題目描述

匯編語(yǔ)言中有一種移位指令叫做循環(huán)左移（ROL），現(xiàn)在有個(gè)簡(jiǎn)單的任務(wù)，就是用字符串模擬這個(gè)指令的運(yùn)算結(jié)>果。對(duì)于一個(gè)給定的字符序列S，請(qǐng)你把其循環(huán)左移K位后的序列輸出。例如，字符序列S=”abcXYZdef”,要求輸>出循環(huán)左移3位后的結(jié)果，即“XYZdefabc”。是不是很簡(jiǎn)單？OK，搞定它！

方法一 時(shí)間復(fù)雜度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;
    }
}

方法二 時(shí)間復(fù)雜度 O(n) 空間復(fù)雜度 O(1)

假設(shè)，輸入進(jìn)來(lái)的是 abcdef 我要反轉(zhuǎn) n= 3
1先反轉(zhuǎn)前面的 abc -> cba
就得到字符串 cbadef

2. 反轉(zhuǎn)后面的 def -> fed
   就得到字符串 cbafed
3. 整個(gè)字符串進(jìn)行反轉(zhuǎn) cbafed -> defabc
   這個(gè)結(jié)果就出來(lái)了

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;
      
        //先反轉(zhuǎn)前面的    
        reverseStr(c, 0, n - 1);
        //再反轉(zhuǎn)后面的
        reverseStr(c, n, len - 1);
        //最后一起反轉(zhuǎn)
        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;
        }
    }
}