字符串左旋轉：O(n) 時間 O(1) 空間的三種優雅實現

編輯：關於C語言

問題描述

定義左旋操作：將字符串前 k 個字符移至尾部。例：abcdef 左旋 2 位 → cdefab。要求：長度 n 的字符串，時間 O(n)，空間 O(1)。

核心洞察：三次反轉法

將字符串分為 X（前 k 字符）和 Y（剩餘），目標變換 XY → YX。利用反轉性質：

(Xᵀ Yᵀ)ᵀ = Y X

三步驟：

X → Xᵀ（反轉前 k 字符）
Y → Yᵀ（反轉後 n-k 字符）
整體反轉 (Xᵀ Yᵀ) → YX

示例：`abcdef` 左旋 3 位（k=3）

原始：abc def
步驟1：cba def   (X 反轉)
步驟2：cba fed   (Y 反轉)
步驟3：def abc   (整體反轉) → 目標結果

C 語言實現

#include <stdio.h>
#include <string.h>

// 反轉 [start, end] 區間字符
char *reverse(char *start, char *end) {
    char tmp;
    while (start < end) {
        tmp = *start;
        *start++ = *end;
        *end-- = tmp;
    }
    return start; // 返回值未實際使用，保留兼容
}

// 左旋轉 pos 位
char *left_rotate(char *s, int pos) {
    int len = strlen(s);
    if (pos >= len || pos < 0) return s; // 邊界檢查
    
    reverse(s, s + pos - 1);       // 反轉前 pos 字符
    reverse(s + pos, s + len - 1); // 反轉後 len-pos 字符
    reverse(s, s + len - 1);       // 整體反轉
    return s;
}

int main() {
    char s[] = "abcdefghij";
    puts(left_rotate(s, 3)); // 輸出: defghijabc
    return 0;
}

另外兩種線性方案

1. 兩指針逐步交換（Juggling Algorithm）

將數組視為 gcd(n, k) 個環，每環內元素循環移位。同為 O(n) 時間、O(1) 空間，代碼稍繁瑣，適合理解循環置換本質。

2. STL `std::rotate` 一行解決

#include <algorithm>
#include <string>

std::string left_rotate_stl(std::string s, int pos) {
    std::rotate(s.begin(), s.begin() + pos, s.end());
    return s;
}

std::rotate 內部同樣採用三次反轉或 Juggling 算法，C++ 程序員首選。

延伸：循環右移 K 位

右移 K 位等價於左移 (n - K % n) 位。同樣適用三次反轉：

void right_rotate(int *arr, int n, int k) {
    k %= n;
    reverse(arr, arr + n - k - 1);
    reverse(arr + n - k, arr + n - 1);
    reverse(arr, arr + n - 1);
}