解題說明
題目描述
給定一個小寫英文字串 s 和一個二維陣列 shifts，其中 shifts[i] = [start, end, direction]：
- 若
direction == 1，將s[start]到s[end]的所有字元向後移動一位（z → a 循環） - 若
direction == 0，將s[start]到s[end]的所有字元向前移動一位（a → z 循環）
依序應用所有 shifts 後，回傳最終字串。
範例：s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
- [0,1,0]：s = "zac"（a→z, b→a）
- [1,2,1]：s = "zbd"（a→b, c→d）
- [0,2,1]：s = "ace"（z→a, b→c, d→e） → 答案："ace"
解題思路
差分陣列 + 前綴和
暴力解法：對每個操作 [start, end, direction]，逐一修改 s[start] 到 s[end] 的字元，時間 O(n × k)，k 為操作數，效率差。
核心思路：用差分陣列批量記錄移位量，最後一次性計算每個位置的總移位量。
差分陣列：
diff[i]：在位置 i 開始新增的移位量（相對於前一位置的變化量）- 對操作
[start, end, direction]（direction=1 表示 +1，direction=0 表示 -1）：diff[start] += d（d = 1 或 -1）diff[end+1] -= d
對 diff 做前綴和，即得每個位置的總移位量 shift[i]。
對每個字元應用移位：
s[i] = (s[i] - 'a' + shift[i] % 26 + 26) % 26 + 'a'
加 26 確保結果非負（shift 可能為負數），再 mod 26 取循環餘數。
時間複雜度：O(n + k)，其中 n 為字串長度，k 為操作次數。
C++ 解法
複雜度分析
時間複雜度
O(n + k)，其中 n 為字串長度，k 為操作次數（shifts 的大小）。
- 建立差分陣列：O(k)，每個操作修改兩個位置。
- 計算前綴和並應用移位：O(n)，線性遍歷。
- 總計：O(n + k)，遠優於暴力法的 O(n × k)。
空間複雜度
O(n)，需要差分陣列（長度 n+1）。若允許原地修改字串，不計輸出的話額外空間為 O(n)。
虛擬碼
1. Initialize diff array of size (n+1) to all zeros 2. For each shift [start, end, direction]: a. d = (direction == 1) ? +1 : -1 b. diff[start] += d c. diff[end+1] -= d 3. runningShift = 0 4. For i from 0 to n-1: a. runningShift += diff[i] b. shifted = ((s[i] - 'a') + runningShift % 26 + 26) % 26 c. s[i] = 'a' + shifted 5. Return s
其他解法
替代方案
方案一：暴力逐字元更新
對每個操作 [start, end, direction]，用迴圈對 s[start] 到 s[end] 的每個字元執行移位。
- 優點：邏輯最直觀，無需額外資料結構。
- 缺點：時間 O(n × k)，當 n=5×10^4 且 k=5×10^4 時需 2.5×10^9 操作，完全超時。
方案二：排序事件點（掃描線）
將每個操作拆成「在 start 增加 d」和「在 end+1 減少 d」兩個事件，排序後用掃描線（sweep line）從左到右累計移位量。
- 優點：概念上與差分陣列相同，且在操作範圍不規則（如操作非常稀疏）時更直觀。
- 缺點：排序事件點需要 O(k log k) 時間，而差分陣列直接索引插入是 O(k)，且差分陣列在 n 確定的情況下不需要排序，更簡單直接。
方案三：分段樹（Segment Tree with Lazy Propagation）
用懶惰線段樹支援區間加法（每次操作 O(log n)）和點查詢（O(log n)）。
- 優點：支援在線查詢（操作過程中隨時查詢字元），適合動態場景。
- 缺點：對本題（所有操作批量完成後一次輸出）屬於過度設計；差分陣列 O(n + k) 整體更優，程式碼也更簡單。
延伸思考
延伸問題
-
移位量不為 1 而是任意整數：若每次操作的移位量可以是任意整數（如 +3 或 -7），差分陣列方案完全適用，只需將
d = shift[2]（已是整數）而非 ±1；最終前綴和 mod 26 即可。這是本題的自然推廣，也是 LC 848（Shifting Letters I）的擴展。 -
二維差分陣列：若問題推廣到矩陣——對矩形子矩陣中每個字符執行移位，可用二維差分陣列。對矩形
(r1,c1)到(r2,c2)加 d：diff[r1][c1] += d,diff[r1][c2+1] -= d,diff[r2+1][c1] -= d,diff[r2+1][c2+1] += d；最後做二維前綴和還原。 -
字符移位 + 查詢：若在所有操作之後，還需要對任意索引執行「查詢當前字符」的操作，而操作與查詢穿插進行（在線問題），差分陣列無法直接支援。可改用線段樹（懶惰標記 lazy propagation）支援 O(log n) 的區間更新和 O(log n) 的單點查詢，是差分陣列方案面對在線場景的通用升級路徑。