LeetCode 874. 模拟行走机器人

🔗 题目信息

题目链接：874. Walking Robot Simulation
难度：中等
核心考点：方向控制 + 哈希优化 + 模拟

💡 核心思路

本题本质是一个网格模拟问题：

机器人从原点 $(0,0)$ 出发，初始朝北（上），根据指令进行移动或转向，同时要避开障碍物。

🧠 指令解析

-2：左转 90°
-1：右转 90°
1 ~ 9：向当前方向前进对应步数

🚀 解题关键

1️⃣ 方向表示（核心技巧）

用数组表示方向（非常经典）：

1

北 → 东 → 南 → 西

用向量表示：

1

dirs = [(0,1), (1,0), (0,-1), (-1,0)]

👉 当前方向用 d 表示：

左转：d = (d + 3) % 4
右转：d = (d + 1) % 4

2️⃣ 障碍物优化（重点）

👉 必须用 set！否则会超时

把障碍物转成哈希集合：

1

obstacles_set = set(map(tuple, obstacles))

👉 查询是否有障碍：O(1)

3️⃣ 一步一步走（避免“穿墙”）

⚠️ 不能一次跳 k 步！

必须这样：

1

一步一步走，每一步都判断是否撞障碍

4️⃣ 记录最大距离

题目要求：

1

返回距离原点的最大欧几里得距离的平方

👉 即：

$$x^2 + y^2$$

🐍 Python 工程实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


from typing import List

class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        # 方向：北、东、南、西
        dirs = [(0,1), (1,0), (0,-1), (-1,0)]
        d = 0  # 初始朝北

        x = y = 0
        max_dist = 0

        # 障碍物哈希化
        obstacles_set = set(map(tuple, obstacles))

        for cmd in commands:
            if cmd == -2:  # 左转
                d = (d + 3) % 4
            elif cmd == -1:  # 右转
                d = (d + 1) % 4
            else:
                # 一步一步走
                dx, dy = dirs[d]
                for _ in range(cmd):
                    nx, ny = x + dx, y + dy
                    if (nx, ny) in obstacles_set:
                        break
                    x, y = nx, ny
                    max_dist = max(max_dist, x*x + y*y)

        return max_dist

⚡ 复杂度分析

时间复杂度：$O(n + k)$
- $n$ 为指令数量
- $k$ 为总移动步数（最多 9n）
空间复杂度：$O(m)$
- $m$ 为障碍物数量

🧩 易错点总结

❌ 一次走 k 步（会穿过障碍） ✔ 必须逐步模拟

❌ 用 list 查障碍（超时） ✔ 用 set

❌ 忘记更新最大距离 ✔ 每一步都更新

🧠 一句话总结

👉 方向数组 + 哈希集合 + 逐步模拟 = 本题最优解