困于环中的机器人

标签: 数学字符串模拟

难度: Medium

在无限的平面上，机器人最初位于 (0, 0) 处，面朝北方。注意:

北方向 是y轴的正方向。
南方向 是y轴的负方向。
东方向 是x轴的正方向。
西方向 是x轴的负方向。

机器人可以接受下列三条指令之一：

"G"：直走 1 个单位
"L"：左转 90 度
"R"：右转 90 度

机器人按顺序执行指令 instructions，并一直重复它们。

只有在平面中存在环使得机器人永远无法离开时，返回 true。否则，返回 false。

示例 1：

输入：instructions = "GGLLGG"
输出：true
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“G”:移动一步。位置:(0,2).方向:北。
“L”:逆时针旋转90度。位置:(0,2).方向:西。
“L”:逆时针旋转90度。位置:(0,2)方向:南。
“G”:移动一步。位置:(0,1)方向:南。
“G”:移动一步。位置:(0,0)方向:南。
重复指令，机器人进入循环:(0,0)——>(0,1)——>(0,2)——>(0,1)——>(0,0)。
在此基础上，我们返回true。

示例 2：

输入：instructions = "GG"
输出：false
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“G”:移动一步。位置:(0,2).方向:北。
重复这些指示，继续朝北前进，不会进入循环。
在此基础上，返回false。

示例 3：

输入：instructions = "GL"
输出：true
解释：机器人最初在(0,0)处，面向北方。
“G”:移动一步。位置:(0,1)方向:北。
“L”:逆时针旋转90度。位置:(0,1).方向:西。
“G”:移动一步。位置:(- 1,1)方向:西。
“L”:逆时针旋转90度。位置:(- 1,1)方向:南。
“G”:移动一步。位置:(- 1,0)方向:南。
“L”:逆时针旋转90度。位置:(- 1,0)方向:东方。
“G”:移动一步。位置:(0,0)方向:东方。
“L”:逆时针旋转90度。位置:(0,0)方向:北。
重复指令，机器人进入循环:(0,0)——>(0,1)——>(- 1,1)——>(- 1,0)——>(0,0)。
在此基础上，我们返回true。

提示：

1 <= instructions.length <= 100
instructions[i] 仅包含 'G', 'L', 'R'

Submission

运行时间: 23 ms

内存: 16.1 MB

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        x, y, d = 0, 0, 0
        for ch in instructions:
            if ch == 'G' and d % 360 == 0:
                y += 1
            elif ch == 'G' and (d % 360 == 270 or d % 360 == -90):
                x -= 1
            elif ch == 'G' and (d % 360 == 180 or d % 360 == -180):
                y -= 1
            elif ch == 'G' and (d % 360 == 90 or d % 360 == -270):
                x += 1
            elif ch == 'L':
                d -= 90
            elif ch == 'R':
                d += 90
        return (x == 0 and y == 0) or d % 360 != 0

Explain

本题解的关键思路是模拟机器人的移动和转向，并检查一遍指令后机器人的状态。机器人如果在执行一轮指令后返回到起点或者朝向非北方向（说明它的路径将会是闭环），则表示机器人的行动是有界的。在代码中，使用变量x, y来记录机器人在平面上的位置，d来记录当前的方向（用角度表示，北为0度，东90度，南180度，西270度或-90度）。根据指令'G', 'L', 'R'更新这些变量。最后，检查机器人是否回到原点(x = 0, y = 0)或方向不为北(d % 360 != 0)，如果满足任一条件，则返回true，表示机器人的运动是有界的。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        x, y, d = 0, 0, 0  # 初始化位置和方向
        for ch in instructions:
            if ch == 'G':  # 如果指令是'G'，根据当前方向移动机器人
                if d % 360 == 0:
                    y += 1
                elif d % 360 == 270 or d % 360 == -90:
                    x -= 1
                elif d % 360 == 180 or d % 360 == -180:
                    y -= 1
                elif d % 360 == 90 or d % 360 == -270:
                    x += 1
            elif ch == 'L':  # 如果指令是'L'，逆时针转90度
                d -= 90
            elif ch == 'R':  # 如果指令是'R'，顺时针转90度
                d += 90
        return (x == 0 and y == 0) or d % 360 != 0  # 检查是否回到原点或方向改变

Explore

在算法中，如果机器人在执行一轮指令后返回到原点，无论之后如何重复这些指令，机器人都会保持在原点，或者沿着一个循环路径行动。如果机器人方向改变（即不再朝北），这意味着在重复指令后，机器人将开始在一个闭环路径上移动，最终形成一个有限的循环区域。因此，这两种情况下机器人的运动都是有界的。

模360的操作能有效处理方向，因为角度加减后可能超过360度或小于0度，模360可以将这些值规范化到[0, 360)的范围内。这样处理后，可以保证方向的计算始终有效，无论多少次旋转，方向总是被正确地处理。

使用角度表示方向的优势在于直观和易于处理。通过简单的加减操作即可模拟实际的转向动作。然而，这种方法的缺点包括可能出现的额外计算（如模360操作）以及在某些情况下可能不如使用向量或矩阵运算直接，特别是在更复杂的空间运动模拟中。

本算法在处理每个指令时进行一次循环，其时间复杂度为O(n)，n是指令长度。对于非常长的指令序列，这种处理方法仍然有效，但性能瓶颈可能在于处理大量数据时的时间消耗。当输入极大时，执行时间会线性增长，这可能导致处理速度变慢，尤其在资源受限的环境下更为明显。