C語言字符串左旋轉 K 位的三種實現方案對比

C語言字符串左旋轉 K 位的三種實現方案對比

字符串左旋轉是經典面試題。給定字符串 "AABCD"，左旋 1 位得 "ABCDA"，左旋 2 位得 "BCDAA"。本文展示三種不同思路的實現，並分析優劣。

方案一：暴力移位法（教學用）

每次左旋 1 位，重複 k 次。時間複雜度 O(n×k)，效率最低，僅供理解基本概念。

方案二：輔助數組法（穩健）

申請臨時空間存放結果，一次性完成旋轉。時間 O(n)，空間 O(n)。代碼見文章 194912 方法一。

方案三：三步反轉法（最優）

原地操作，無需額外空間。核心邏輯：

1. 反轉前 k 個字符
2. 反轉第 k+1 到末尾字符
3. 反轉整個字符串

以下是封裝良好的完整實現：

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

void reverse(char *str, int len) {
    assert(str);
    char *start = str;
    char *end = str + len - 1;
    while (start < end) {
        char tmp = *start;
        *start = *end;
        *end = tmp;
        start++;
        end--;
    }
}

void left_rotate(char *str, int len, int k) {
    assert(str);
    if (k >= len) {
        printf("旋轉位數超出字符串長度\n");
        return;
    }
    reverse(str, len);                 // 步驟 1：整體反轉
    reverse(str, len - k);             // 步驟 2：反轉前 len-k 個（原後段）
    reverse(str + len - k, k);         // 步驟 3：反轉後 k 個（原前段）
}

int main(void) {
    char str[] = "aabcd";
    int len = strlen(str);
    int k;
    printf("請輸入要旋轉的字符個數：");
    scanf("%d", &k);
    left_rotate(str, len, k);
    printf("旋轉後：%s\n", str);
    return 0;
}

方案對比總結