ACM 題目 T1：數組插入刪除的精煉算法實現

ACM 題目 T1：數組插入刪除的精煉算法實現

題目鏈接：https://acm.swust.edu.cn/oj/problem/860/

題目分析

操作數據量小，鏈表大材小用，用數組模擬即可。
命令格式：A k ch 在位置 k 插入字符 ch；D ch 刪除所有字符 ch；END 結束當前組操作。

關鍵代碼片段

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

char str[105], cmd[3], ch[1];

int main() {
    int i, j, k, l;
    while (scanf("%s", str) == 1) {           // 多組測試數據
        while (scanf("%s", cmd) == 1 && strcmp(cmd, "END") != 0) {
            scanf("%s", ch);
            l = strlen(str);
            if (cmd[0] == 'A') {              // A 操作：插入
                scanf("%d", &k);
                --k;                          // 轉為 0 基下標
                if (k > l) k = l;             // 越界則插在末尾
                // 後移騰出位置
                for (i = l - 1; i >= k; --i)
                    str[i + 1] = str[i];
                str[k] = ch[0];
                str[++l] = '\0';              // 更新長度並加結束符
            } else {                          // D 操作：刪除
                // 精妙的單趟掃描刪除並移位
                for (i = j = 0; i < l; ++i) {
                    if (str[i] != ch[0])
                        str[j++] = str[i];
                }
                str[j] = '\0';
            }
        }
        puts(str);
    }
    return 0;
}

算法亮點

1. 插入：從末尾向前逆序移動元素，避免覆蓋，時間複雜度 O(n)，適合小數據量。
2. 刪除：雙指針 i（讀）j（寫）單趟掃描，保留非目標字符，原地壓縮，同樣 O(n)，代碼極其簡潔高效。

註：大數據量場景下應考慮鏈表或更高級數據結構以降低移動開銷。