給定字元陣列
s，原地反轉字串。必須使用 O(1) 額外空間。
Example:
Input: s = [‘h’,‘e’,‘l’,‘l’,‘o’] Output: [‘o’,‘l’,‘l’,‘e’,‘h’]
Intuition
TIP
核心思路：左右指針相向移動，逐一交換字元。
- 反轉陣列最經典的做法就是首尾交換
- 兩個指針分別從頭尾出發，向中間靠攏，每步交換
Approaches
1. Standard Library — O(n) / O(1)
- Idea: 直接呼叫
reverse()函式 - Time:
O(n) - Space:
O(1)
class Solution {
fun reverseString(s: CharArray): Unit {
s.reverse()
}
}⭐ 2. Two Pointers Swap — O(n) / O(1)
- Idea: 左右指針相向移動，交換對應位置的字元
- Time:
O(n)- 遍歷一半的陣列 - Space:
O(1)- 只用兩個指針和一個暫存
class Solution {
fun reverseString(s: CharArray): Unit {
var left = 0
var right = s.size - 1
while (left < right) {
val temp = s[left]
s[left] = s[right]
s[right] = temp
left++
right--
}
}
}WARNING
Kotlin 的 also 可以讓交換更簡潔：s[left] = s[right].also { s[right] = s[left] }，但面試中 temp 變數更清晰。
🔑 Takeaways
- Pattern: 相向雙指針交換，是原地反轉的基礎操作
- Key trick: 此技巧是許多進階問題的子程序（如反轉句子中的單字、旋轉陣列等）