一個機器人在無限平面上從原點 (0,0) 面朝北方出發。給定一組指令
instructions（G=前進、L=左轉、R=右轉），機器人會無限重複執行這些指令。判斷是否存在一個圓使得機器人永遠不會離開這個圓。
Example:
Input: instructions = “GGLLGG” Output: true (執行一次後回到原點)
Intuition
TIP
核心思路：執行一輪指令後，若機器人回到原點或方向不朝北，則一定會形成有界循環。
- 執行一輪後回到原點：顯然有界
- 執行一輪後方向不朝北：
- 朝南：2 輪後回到原點
- 朝東或朝西：4 輪後回到原點
- 唯一無界的情況：執行一輪後不在原點且仍朝北（每輪都往同一方向前進）
Approaches
⭐ 1. Single-Pass Simulation — O(n) / O(1)
- Idea: 模擬執行一輪指令，檢查結束後的位置和方向
- Time:
O(n)- n 為指令長度 - Space:
O(1)
class Solution {
fun isRobotBounded(instructions: String): Boolean {
// 方向：0=北, 1=東, 2=南, 3=西
val dx = intArrayOf(0, 1, 0, -1)
val dy = intArrayOf(1, 0, -1, 0)
var x = 0
var y = 0
var dir = 0 // 北
for (ch in instructions) {
when (ch) {
'G' -> {
x += dx[dir]
y += dy[dir]
}
'L' -> dir = (dir + 3) % 4 // 左轉 = +3 (mod 4)
'R' -> dir = (dir + 1) % 4 // 右轉 = +1 (mod 4)
}
}
// 回到原點，或方向不朝北（最多 4 輪會回到原點）
return (x == 0 && y == 0) || dir != 0
}
}2. Four-Round Simulation Check — O(n) / O(1)
- Idea: 直接模擬四輪指令，檢查是否回到原點（用於驗證理論的正確性）
- Time:
O(n)- 4n 仍為 O(n) - Space:
O(1)
class Solution {
fun isRobotBounded(instructions: String): Boolean {
val dx = intArrayOf(0, 1, 0, -1)
val dy = intArrayOf(1, 0, -1, 0)
var x = 0
var y = 0
var dir = 0
// 最多 4 輪必定回到原點（如果會形成循環）
repeat(4) {
for (ch in instructions) {
when (ch) {
'G' -> { x += dx[dir]; y += dy[dir] }
'L' -> dir = (dir + 3) % 4
'R' -> dir = (dir + 1) % 4
}
}
}
return x == 0 && y == 0
}
}🔑 Takeaways
- Pattern: 週期性行為分析——觀察一個週期後的狀態即可判斷長期行為
- Key trick: 方向變化最多 4 輪一循環（360 度），所以只需一輪模擬後檢查方向即可判斷有界性