LeetCode 874. Walking Robot Simulation 题解：Go 实现「方向数组 + 障碍物哈希」的机器人模拟行走

LeetCode 874. Walking Robot Simulation 题解Go 实现「方向数组 障碍物哈希」的机器人模拟行走【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇文章基于 LeetCode-Go 仓库中 leetcode/0874.Walking-Robot-Simulation/README.md 的题目解析与 Go 解法展开结合仓库内的源码与测试用例完整讲解 874. Walking Robot Simulation 的题意、数据结构建模、逐行代码实现、复杂度分析以及本地测试方法。读完本文你将掌握用方向数组描述朝向、用哈希集合做 O(1) 障碍物判定的通用模拟思路并能直接运行仓库测试验证结果。题目描述原题A robot on an infinite XY-plane starts at point(0, 0)and faces north. The robot can receive one of three possible types ofcommands:-2: turn left90degrees,-1: turn right90degrees, or1 k 9: move forwardkunits.Some of the grid squares areobstacles. Theithobstacle is at grid pointobstacles[i] (xi, yi).If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)Returnthe maximum Euclidean distance that the robot will be from the originsquared(i.e. if the distance is5, return25).Note:North means Y direction.East means X direction.South means -Y direction.West means -X direction.Example 1:Input: commands [4,-1,3], obstacles [] Output: 25 Explanation: The robot starts at (0, 0): 1. Move north 4 units to (0, 4). 2. Turn right. 3. Move east 3 units to (3, 4). The furthest point away from the origin is (3, 4), which is 32 42 25 units away.Example 2:Input: commands [4,-1,4,-2,4], obstacles [[2,4]] Output: 65 Explanation: The robot starts at (0, 0): 1. Move north 4 units to (0, 4). 2. Turn right. 3. Move east 1 unit and get blocked by the obstacle at (2, 4), robot is at (1, 4). 4. Turn left. 5. Move north 4 units to (1, 8). The furthest point away from the origin is (1, 8), which is 12 82 65 units away.Constraints:1 commands.length 10^4commands[i]is one of the values in the list[-2,-1,1,2,3,4,5,6,7,8,9].0 obstacles.length 10^4-3 * 10^4 xi, yi 3 * 10^4The answer is guaranteed to be less than2^31.题目大意机器人在一个无限大小的 XY 网格平面上行走从点(0, 0)处开始出发面向北方。该机器人可以接收以下三种类型的命令commands-2向左转 90 度-1向右转 90 度1 x 9向前移动x个单位长度在网格上有一些格子被视为障碍物obstacles。第i个障碍物位于网格点obstacles[i] (xi, yi)。机器人无法走到障碍物上它将会停留在障碍物的前一个网格方块上但仍然可以继续尝试进行该路线的其余部分。返回从原点到机器人所有经过的路径点坐标为整数的最大欧式距离的平方即如果距离为 5则返回 25。注意北表示 Y 方向。东表示 X 方向。南表示 -Y 方向。西表示 -X 方向。解题思路用数据结构描述机器人的行为这个题的核心难点在于怎么用编程语言去描述机器人的面向方向与单步移动。原文档leetcode/0874.Walking-Robot-Simulation/README.md给出了非常精炼的数据结构建模direct : 0 // direct 表示机器人移动方向0 1 2 3北东南西默认朝北 x, y : 0, 0 // 表示当前机器人所在横纵坐标位置默认为 (0, 0) directX : []int{0, 1, 0, -1} directY : []int{1, 0, -1, 0} // 组合 directX、directY 和 direct表示机器人往某一个方向移动 nextX : x directX[direct] nextY : y directY[direct]这套建模的核心思想可以拆成三点方向用下标表达将「北、东、南、西」四个方向映射到下标0、1、2、3。结合两个方向增量数组(directX[direct], directY[direct])就是朝direct方向走一步的坐标增量direct 0北(0, 1)direct 1东(1, 0)direct 2南(0, -1)direct 3西(-1, 0)转向用取模实现右转 90 度等价于方向下标1再对 4 取模左转 90 度等价于方向下标3再对 4 取模等价于-1的模运算安全写法避免出现负数下标。障碍物用哈希集合将所有障碍物坐标存入map每次准备迈出下一步前先查询目标格是否是障碍物是则原地停下并结束当前这条移动命令但后续命令继续执行。完整 Go 代码仓库中的完整实现位于 874. Walking Robot Simulation.gopackage leetcode func robotSim(commands []int, obstacles [][]int) int { m : make(map[[2]int]struct{}) for _, v : range obstacles { if len(v) ! 0 { m[[2]int{v[0], v[1]}] struct{}{} } } directX : []int{0, 1, 0, -1} directY : []int{1, 0, -1, 0} direct, x, y : 0, 0, 0 result : 0 for _, c : range commands { if c -2 { direct (direct 3) % 4 continue } if c -1 { direct (direct 1) % 4 continue } for ; c 0; c-- { nextX : x directX[direct] nextY : y directY[direct] if _, ok : m[[2]int{nextX, nextY}]; ok { break } tmpResult : nextX*nextX nextY*nextY if tmpResult result { result tmpResult } x nextX y nextY } } return result }代码逐段解析1. 障碍物预处理map[[2]int]struct{}m : make(map[[2]int]struct{}) for _, v : range obstacles { if len(v) ! 0 { m[[2]int{v[0], v[1]}] struct{}{} } }使用 Go 的复合键类型[2]int直接作为 map 的 key免去了拼接字符串或自定义哈希的麻烦值为struct{}空结构体不占用额外内存这是 Go 中实现「集合」的标准写法if len(v) ! 0用于防御性地跳过空切片。这一点并非多余——仓库的测试用例中 case 1 传入的正是obstacles: [][]int{{}}一个包含空切片的空障碍物列表有了这层判断才能稳定通过测试。2. 方向表与状态初始化directX : []int{0, 1, 0, -1} directY : []int{1, 0, -1, 0} direct, x, y : 0, 0, 0 result : 0direct初始为 0对应面向北方Yresult保存迄今经过路径点中最大的x² y²注意题目要求返回的是距离的平方因此全程使用整数运算即可无需开方。3. 命令主循环转向命令for _, c : range commands { if c -2 { direct (direct 3) % 4 continue } if c -1 { direct (direct 1) % 4 continue } ... }c -2表示左转 90 度(direct 3) % 4等价于逆时针旋转一格方向c -1表示右转 90 度(direct 1) % 4顺时针旋转一格方向使用% 4保证方向下标永远落在[0, 3]区间内是处理环形状态转移的经典手法。4. 命令主循环移动命令逐格探测for ; c 0; c-- { nextX : x directX[direct] nextY : y directY[direct] if _, ok : m[[2]int{nextX, nextY}]; ok { break } tmpResult : nextX*nextX nextY*nextY if tmpResult result { result tmpResult } x nextX y nextY }移动命令c的取值范围是[1, 9]代码采用逐格移动的方式每走一格就构造下一个坐标(nextX, nextY)先在哈希集合中查询下一格是否为障碍物若是则break——机器人停留在当前格但外层命令循环继续后续命令仍然生效这与题意完全一致每成功走一格就更新result保证最终返回的是所有经过点中离原点最远的那个距离平方。复杂度分析设命令数组长度为NN 10^4障碍物数量为MM 10^4单条移动命令最大步长为k_max 9时间复杂度O(N * k_max M)。障碍物预处理遍历一次为O(M)主循环中转向命令是O(1)移动命令按c逐格推进总步数上界为9N。由于k_max是常数 9可以近似表述为O(N M)空间复杂度O(M)。主要开销是存放障碍物的哈希集合m其余只用了常数个变量。之所以可以采用逐格移动正是因为k_max很小不超过 9且坐标范围有限[-3*10^4, 3*10^4]逐格探测的常数开销可以忽略同时逐格探测天然满足了「遇到障碍物停在上一格」的语义无需额外处理整段跳跃后回退的复杂边界。测试用例与本地验证仓库为本题配套了单元测试 874. Walking Robot Simulation_test.go采用 Go 标准的表驱动table-driven测试风格用例commandsobstacles期望输出case 1[4, -1, 3][][]int{{}}空25case 2[4, -1, 4, -2, 4][[2, 4]]65其中 case 1 对应题目示例 1先向北 4 步再向东 3 步最远点为(3, 4)3² 4² 25case 2 对应题目示例 2向东时被(2, 4)处障碍物挡住停在(1, 4)再向北到(1, 8)最远距离平方1² 8² 65。在仓库根目录下可单独运行该题的测试go test -v ./leetcode/0874.Walking-Robot-Simulation/ -run Test_robotSim如需生成整个仓库的覆盖率报告可以运行仓库根目录的 gotest.sh 脚本其核心命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...要求 Go 1.10仓库 go.mod 声明版本为 Go 1.19./gotest.sh边界情况与易错点总结空障碍物列表测试中传入的[][]int{{}}含空切片预处理时的len(v) ! 0判断必不可少否则访问v[0]会越界 panic左转与取模左转不能用direct - 1直接处理会出现-1下标必须写成(direct 3) % 4障碍物语义被障碍物挡住后只是本次移动提前结束机器人位置不后退后续命令照常执行返回值是平方题目要求返回最大欧式距离的平方全程比较nextX*nextX nextY*nextY即可不要开方math.Sqrt会引入浮点误差且浪费性能答案范围约束保证答案小于2^31因此int累加不会溢出在 64 位平台上更无需担心。小结Walking Robot Simulation 是一道典型的模拟题本身逻辑并不复杂真正的价值在于如何用最少的数据结构把方向、转向、障碍物判定表达得清晰且不易出错。本仓库给出的 Go 解法用「方向数组 取模转向 map[[2]int]struct{}哈希集合」三件套在保证O(N M)复杂度与代码可读性的同时还通过防御性的空切片判断覆盖了测试中的边界输入是一份值得直接参考和复用的模板实现。完整题目描述与解法讲解见 leetcode/0874.Walking-Robot-Simulation/README.md。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考