1041. Robot Bounded In Circle

Medium

Description

一個機器人在無限平面上從原點 (0,0) 面朝北方出發。給定一組指令 instructions（G=前進、L=左轉、R=右轉），機器人會無限重複執行這些指令。判斷是否存在一個圓使得機器人永遠不會離開這個圓。

Example:

Input: instructions = “GGLLGG” Output: true (執行一次後回到原點)

Intuition#

核心思路：執行一輪指令後，若機器人回到原點或方向不朝北，則一定會形成有界循環。

執行一輪後回到原點：顯然有界
執行一輪後方向不朝北：
- 朝南：2 輪後回到原點
- 朝東或朝西：4 輪後回到原點
唯一無界的情況：執行一輪後不在原點且仍朝北（每輪都往同一方向前進）

Approaches#

⭐1: 一輪模擬#

概念: 模擬執行一輪指令，檢查結束後的位置和方向
時間複雜度: O(n) - n 為指令長度
空間複雜度: 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: 四輪模擬驗證#

概念: 直接模擬四輪指令，檢查是否回到原點（用於驗證理論的正確性）
時間複雜度: O(n) - 4n 仍為 O(n)
空間複雜度: 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: 週期性行為分析——觀察一個週期後的狀態即可判斷長期行為
關鍵技巧: 方向變化最多 4 輪一循環（360 度），所以只需一輪模擬後檢查方向即可判斷有界性