題⽬描述

彙編語⾔中有⼀種移位指令叫做循環左移（ ROL ），現在有個簡單的任務，就是⽤字符串模擬這個指令的運算結果。對於⼀個給定的字符序列 S ，請你把其循環左移 K 位後的序列輸出。例如，字符序列S=”abcXYZdef” ,要求輸出循環左移3位後的結果，即“ XYZdefabc ”。是不是很簡單？OK，搞定它！

思路及解答

這道題⽬的意思就是將前⾯ n 位，移動到後⾯，那麼我們可以直接從第 n+1 位開始，遍歷到最後⼀個，再拼接上前⾯ n 個。

暴力移位

通過k次單步左移實現循環左移。將第一個字符保存，其餘字符前移，最後字符放到末尾

public class Solution {

    public String leftRotateString(String str, int n) {
        if (str == null || str.length() == 0 || n <= 0) {
            return str;
        }
        
        char[] chars = str.toCharArray();
        int len = chars.length;
        n %= len; // 處理n大於字符串長度的情況
        
        // 執行n次單步左移
        for (int k = 0; k < n; k++) {
            // 單步左移：保存首字符，其餘前移，最後放回首字符
            char firstChar = chars[0];
            for (int i = 0; i < len - 1; i++) {
                chars[i] = chars[i + 1];
            }
            chars[len - 1] = firstChar;
        }
        
        return new String(chars);
    }
}

• 時間複雜度：O(k×n)，其中k為移動次數，n為字符串長度
• 空間複雜度：O(1)，只使用固定額外空間

字符串切片法（推薦）

值得注意的是， n 可能⼤於 str 的⻓度，那麼這種情況下我們應該先對 str 的⻓度取餘，保持嚴謹。即是： n = n % str.length(); 。

public class Solution {

    public String LeftRotateString(String str, int n) {
        if (str == null || str.length() == 0 || n <= 0) {
            return str;
        }
        String ret = "";
        n = n % str.length();
        for (int i = n; i < str.length(); ++i) {
            ret += str.charAt(i);
        }
        
        for (int i = 0; i < n; ++i) {
            ret += str.charAt(i);
        }
        return ret;
    }

}

• 時間複雜度 O(n)
• 空間複雜度 O(n) 。

或者可以用substring 的API

public class Solution {
    public String leftRotateString(String str, int n) {
        if (str == null || str.length() == 0 || n <= 0) {
            return str;
        }
        
        int len = str.length();
        n %= len; // 處理n大於字符串長度的情況
        
        // 直接截取並拼接：後部分 + 前部分
        return str.substring(n) + str.substring(0, n);
    }
}

• 時間複雜度：O(n)，substring操作需要線性時間
• 空間複雜度：O(n)，創建新的字符串對象

三次反轉（數學優美）

利用數學規律：BA = (A'B')'，通過三次反轉實現循環左移。

分別反轉前n位、剩餘部分，最後整體反轉

public class Solution {

    public String leftRotateString(String str, int n) {
        if (str == null || str.length() == 0 || n <= 0) {
            return str;
        }
        
        char[] chars = str.toCharArray();
        int len = chars.length;
        n %= len;
        
        if (n == 0) return str; // 移動0位直接返回
        
        // 第一步：反轉前n個字符
        reverse(chars, 0, n - 1);
        // 第二步：反轉剩餘字符
        reverse(chars, n, len - 1);
        // 第三步：整體反轉
        reverse(chars, 0, len - 1);
        
        return new String(chars);
    }
    
    /**
     * 反轉字符數組中指定範圍的字符
     * @param chars 字符數組
     * @param start 起始索引
     * @param end 結束索引
     */
    private void reverse(char[] chars, int start, int end) {
        while (start < end) {
            // 交換首尾字符
            char temp = chars[start];
            chars[start] = chars[end];
            chars[end] = temp;
            start++;
            end--;
        }
    }
}

• 時間複雜度：O(n)，每個字符被訪問兩次
• 空間複雜度：O(1)，原地操作，只使用常數空間