解題說明
題目描述
給定一個小寫英文字串 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) 的單點查詢,是差分陣列方案面對在線場景的通用升級路徑。