題目描述:
給定一個字元陣列 s,原地(in-place)反轉它。必須使用 O(1) 額外空間。
解題思路:
使用雙指標法。設定兩個指標 left 和 right 分別指向陣列的首尾:
s[left] 和 s[right]。left 向右移,right 向左移。left >= right。每次交換將一對對稱位置的字元歸位,遍歷一半陣列即完成反轉。
時間複雜度:O(n) — 雙指標各走 n/2 步,共執行 n/2 次交換。
空間複雜度:O(1) — 只使用兩個指標變數,原地修改。
1. Initialize left = 0, right = length - 1 2. While left < right: a. Swap s[left] and s[right] b. left++, right-- 3. Done (array is reversed in-place)
遞迴法:reverse(s, left, right) 交換首尾後遞迴 reverse(s, left+1, right-1)。時間 O(n),空間 O(n) 遞迴深度。簡潔但遞迴堆疊消耗 O(n) 空間,不滿足 O(1) 空間要求。
使用 STL:直接呼叫 std::reverse(s.begin(), s.end())。面試中通常要求手動實作,但工程上這是最佳選擇。底層實作即為雙指標交換。