LeetCode 题解工作台
模拟行走机器人 II
给你一个在 XY 平面上的 width x height 的网格图， 左下角 的格子为 (0, 0) ， 右上角 的格子为 (width - 1, height - 1) 。网格图中相邻格子为四个基本方向之一（ "North" ， "East" ， "South" 和 "West" ）。一个机器人 …
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · design·结合·模拟
答案摘要
我们记 $mx = width - 1$ 和 $my = height - 1$，则机器人的运动轨迹是一个以 $(0, 0)$ 为左下角，而 $(mx, my)$ 为右上角的矩形的边界。我们可以将机器人的运动轨迹分为四段： 1. 从 $(0, 0)$ 沿着 轴正方向运动到 $(mx, 0)$，此时机器人的朝向为 "East"。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 design·结合·模拟 题型思路
题目描述
给你一个在 XY 平面上的 width x height 的网格图，左下角 的格子为 (0, 0) ，右上角 的格子为 (width - 1, height - 1) 。网格图中相邻格子为四个基本方向之一（"North"，"East"，"South" 和 "West"）。一个机器人 初始 在格子 (0, 0) ，方向为 "East" 。
机器人可以根据指令移动指定的 步数 。每一步，它可以执行以下操作。
- 沿着当前方向尝试 往前一步 。
- 如果机器人下一步将到达的格子 超出了边界 ，机器人会 逆时针 转 90 度，然后再尝试往前一步。
如果机器人完成了指令要求的移动步数，它将停止移动并等待下一个指令。
请你实现 Robot 类：
Robot(int width, int height)初始化一个width x height的网格图，机器人初始在(0, 0)，方向朝"East"。void step(int num)给机器人下达前进num步的指令。int[] getPos()返回机器人当前所处的格子位置，用一个长度为 2 的数组[x, y]表示。String getDir()返回当前机器人的朝向，为"North"，"East"，"South"或者"West"。
示例 1：
输入：
["Robot", "step", "step", "getPos", "getDir", "step", "step", "step", "getPos", "getDir"]
[[6, 3], [2], [2], [], [], [2], [1], [4], [], []]
输出：
[null, null, null, [4, 0], "East", null, null, null, [1, 2], "West"]
解释：
Robot robot = new Robot(6, 3); // 初始化网格图，机器人在 (0, 0) ，朝东。
robot.step(2); // 机器人朝东移动 2 步，到达 (2, 0) ，并朝东。
robot.step(2); // 机器人朝东移动 2 步，到达 (4, 0) ，并朝东。
robot.getPos(); // 返回 [4, 0]
robot.getDir(); // 返回 "East"
robot.step(2); // 朝东移动 1 步到达 (5, 0) ，并朝东。
// 下一步继续往东移动将出界，所以逆时针转变方向朝北。
// 然后，往北移动 1 步到达 (5, 1) ，并朝北。
robot.step(1); // 朝北移动 1 步到达 (5, 2) ，并朝 北 （不是朝西）。
robot.step(4); // 下一步继续往北移动将出界，所以逆时针转变方向朝西。
// 然后，移动 4 步到 (1, 2) ，并朝西。
robot.getPos(); // 返回 [1, 2]
robot.getDir(); // 返回 "West"
提示：
2 <= width, height <= 1001 <= num <= 105step，getPos和getDir总共 调用次数不超过104次。
解题思路
方法一：分类讨论
我们记 和 ，则机器人的运动轨迹是一个以 为左下角，而 为右上角的矩形的边界。我们可以将机器人的运动轨迹分为四段：
- 从 沿着 轴正方向运动到 ，此时机器人的朝向为 "East"。
- 从 沿着 轴正方向运动到 ，此时机器人的朝向为 "North"。
- 从 沿着 轴负方向运动到 ，此时机器人的朝向为 "West"。
- 从 沿着 轴负方向运动到 ，此时机器人的朝向为 "South"。
因此，我们可以将机器人的运动轨迹看作是一个长度为 的循环。对于每次调用 step(num)，我们可以将机器人的当前位置加上 num，然后对 取模，得到机器人的新位置。根据机器人的新位置，我们可以判断出机器人的朝向和坐标。
注意，如果机器人没有移动过，那么它的朝向应该是 "East"。如果机器人移动过，且位置为 ，则机器人的朝向应该是 "South"。
时间复杂度 ，空间复杂度 。
class Robot:
def __init__(self, width: int, height: int):
self.mx = width - 1
self.my = height - 1
self.p = 2 * self.mx + 2 * self.my
self.cur = 0
self.moved = False
def step(self, num: int) -> None:
self.moved = True
self.cur = (self.cur + num) % self.p
def getPos(self) -> List[int]:
d = self.cur
mx, my = self.mx, self.my
if 0 <= d <= mx:
return [d, 0]
if mx < d <= mx + my:
return [mx, d - mx]
if mx + my < d <= 2 * mx + my:
return [mx - (d - (mx + my)), my]
return [0, my - (d - (2 * mx + my))]
def getDir(self) -> str:
d = self.cur
mx, my = self.mx, self.my
if not self.moved:
return "East"
if 1 <= d <= mx:
return "East"
elif mx < d <= mx + my:
return "North"
elif mx + my < d <= 2 * mx + my:
return "West"
return "South"
# Your Robot object will be instantiated and called as such:
# obj = Robot(width, height)
# obj.step(num)
# param_2 = obj.getPos()
# param_3 = obj.getDir()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Looking for a clean approach to handle boundary conditions and direction changes.
- question_mark
Check if the candidate can optimize the position tracking with modulus for wrapping around the grid.
- question_mark
Evaluate the candidate’s ability to simulate multiple commands without unnecessary complexity.
常见陷阱
外企场景- error
Not handling the boundary conditions properly, causing the robot to move out of bounds.
- error
Overcomplicating the direction changes, leading to inefficient code.
- error
Failing to correctly update the robot’s state after each command.
进阶变体
外企场景- arrow_right_alt
Add more complex movement patterns with obstacles in the grid.
- arrow_right_alt
Simulate robot movements in a 3D grid or more complex environments.
- arrow_right_alt
Introduce time-based movements, where the robot’s speed varies depending on the command.