2069. 模拟行走机器人 II 技术解析

2069. 模拟行走机器人 II 技术解析一、题目描述LeetCode 2069. 模拟行走机器人 II在一个width x height的网格图上左下角为(0, 0)右上角为(width-1, height-1)。机器人初始位于(0, 0)方向朝“East”东。机器人可以接受移动指令每次移动一步规则如下沿着当前方向尝试前进一步如果下一步会超出边界则机器人逆时针旋转 90°然后再次尝试前进一步旋转不消耗步数转向后立即走这一步重复直到完成指定的步数。需要实现Robot类支持Robot(int width, int height)初始化网格机器人位于(0,0)朝东。void step(int num)让机器人移动num步。int[] getPos()返回当前坐标[x, y]。String getDir()返回当前方向为North、East、South或West。示例robotRobot(6,3)robot.step(2)# 移动到 (2,0)朝东robot.step(2)# 移动到 (4,0)朝东robot.getPos()# [4,0]robot.getDir()# Eastrobot.step(2)# 移动到 (5,1)朝北robot.step(1)# 移动到 (5,2)朝北robot.step(4)# 移动到 (1,2)朝西robot.getPos()# [1,2]robot.getDir()# West二、问题分析2.1 直接模拟的困境最直观的想法是每步都模拟检查下一步是否出界若出界则转向然后移动。但step(num)中的num最大可达10^5而step总调用次数可达10^4最坏情况下总步数达10^9直接模拟必然超时。2.2 观察机器人的运动规律机器人永远沿着网格的边界移动永远不会进入内部。因为一旦试图离开边界就会转向所以它始终贴着边界逆时针行走东→北→西→南→东……。实际上机器人的路径是一个矩形环从(0,0)出发沿下边界向东到(width-1,0)沿右边界向北到(width-1, height-1)沿上边界向西到(0, height-1)沿左边界向南回到(0,0)。但注意回到(0,0)时方向是南与初始方向东不同。此后机器人会继续沿着这个环逆时针移动永远不会再以“东”方向出现在(0,0)。2.3 状态压缩——环上建模机器人的每一个状态位置 方向都是有限的。我们可以将所有可能的状态按移动顺序排列成一个环除去初始状态后其余状态构成一个长度为L的循环。其中L2*(widthheight)-4L表示从初始状态出发走L步后回到(0,0)但方向为南再走L步则回到(0,0)方向南永远不会回到初始的(0,0)东。因此除了初始状态外其余L个状态形成一个循环。我们可以预先计算出这L个状态按逆时针顺序然后每次移动只需累计步数再根据步数取模定位到对应状态即可。状态列表生成顺序下边界东向从(1,0)到(width-1, 0)共width-1步。右边界北向从(width-1, 1)到(width-1, height-1)共height-1步。上边界西向从(width-2, height-1)到(0, height-1)共width-1步。左边界南向从(0, height-2)到(0, 0)共height-1步。总步数L (width-1)(height-1)(width-1)(height-1) 2*(widthheight)-4。注意每个状态包含坐标(x, y)和方向字符串。三、算法设计3.1 数据结构total_steps记录机器人从初始状态开始已经移动的总步数。states列表长度为L按顺序存储每一步之后的状态位置 方向。states[i]对应移动i1步后的状态索引从 0 开始。3.2 核心操作__init__根据width和height构建states列表初始化total_steps 0。step(num)total_steps num。getPos()若total_steps 0返回[0, 0]。否则计算idx (total_steps - 1) % L返回states[idx]的坐标。getDir()若total_steps 0返回East。否则计算idx (total_steps - 1) % L返回states[idx]的方向。3.3 复杂度分析预处理O(width height)最大O(200)因width, height ≤ 100。每次stepO(1)仅需累加步数无循环操作。每次查询getPos、getDirO(1)仅需取模定位状态。空间复杂度O(width height)仅用于存储状态列表空间开销极小。四、代码实现代码严格遵循题目要求注释清晰、逻辑严谨可直接复制运行贴合面试白板编程规范。fromtypingimportListclassRobot:def__init__(self,width:int,height:int):self.widthwidth self.heightheight self.total_steps0# 记录从初始状态开始的总步数# 预计算所有移动后的状态按逆时针顺序每步对应一个状态self.states[]# 1. 下边界向东移动从 (1,0) 到 (width-1, 0)共 width-1 步forxinrange(1,width):self.states.append((x,0,East))# 2. 右边界向北移动从 (width-1, 1) 到 (width-1, height-1)共 height-1 步foryinrange(1,height):self.states.append((width-1,y,North))# 3. 上边界向西移动从 (width-2, height-1) 到 (0, height-1)共 width-1 步forxinrange(width-2,-1,-1):self.states.append((x,height-1,West))# 4. 左边界向南移动从 (0, height-2) 到 (0, 0)共 height-1 步foryinrange(height-2,-1,-1):self.states.append((0,y,South))# 环的长度即循环周期self.Llen(self.states)# 等于 2*(widthheight)-4defstep(self,num:int)-None:# 累加总步数无需逐步模拟后续通过取模定位状态self.total_stepsnumdefgetPos(self)-List[int]:# 初始状态未移动直接返回 (0,0)ifself.total_steps0:return[0,0]# 计算当前状态在states中的索引取模实现循环定位idx(self.total_steps-1)%self.L x,y,_self.states[idx]return[x,y]defgetDir(self)-str:# 初始状态未移动方向为Eastifself.total_steps0:returnEast# 计算当前状态在states中的索引idx(self.total_steps-1)%self.L _,_,directionself.states[idx]returndirection# 使用示例与题目一致可直接运行验证# robot Robot(6, 3)# robot.step(2)# print(robot.getPos(), robot.getDir()) # [2,0] East五、测试验证以下测试用例覆盖题目示例和边界场景确保代码正确性。测试用例1题目示例验证robotRobot(6,3)robot.step(2)robot.step(2)print(robot.getPos(),robot.getDir())# 预期输出[4,0] Eastrobot.step(2)robot.step(1)robot.step(4)print(robot.getPos(),robot.getDir())# 预期输出[1,2] West输出与题目预期完全一致验证代码核心逻辑正确。测试用例2边界情况验证width2, height2robotRobot(2,2)robot.step(1)# 移动1步到 (1,0)方向Eastrobot.step(1)# 移动1步到 (1,1)方向Northrobot.step(1)# 移动1步到 (0,1)方向Westrobot.step(1)# 移动1步到 (0,0)方向Southprint(robot.getPos(),robot.getDir())# 预期输出[0,0] Southrobot.step(1)# 移动1步转向East到 (1,0)方向Eastprint(robot.getPos(),robot.getDir())# 预期输出[1,0] East边界场景下状态切换和方向变化均符合预期无逻辑漏洞。六、总结核心思想机器人只在边界上逆时针移动状态构成一个固定环。通过预计算环上所有状态将“逐步模拟”转化为“步数累加取模定位”实现O(1)移动和查询彻底解决超时问题。关键点初始状态(0,0)朝东是特殊状态不在循环环上环的长度L 2*(widthheight)-4状态列表需严格按“下边界→右边界→上边界→左边界”的逆时针顺序生成移动num步只需累加总步数查询时通过(total_steps - 1) % L定位到对应状态避免逐步模拟。适用场景任何需要频繁移动且路径固定的机器人模拟问题均可采用类似的“状态预计算循环取模”技巧实现高效模拟。七、拓展思考顺时针转向适配若题目要求机器人出界后顺时针旋转90°只需调整状态列表的生成顺序下边界→右边界→上边界→左边界 改为 下边界→左边界→上边界→右边界同时对应调整方向即可。超大网格优化若网格尺寸极大如width, height ≤ 10^9预先生成状态列表会导致内存溢出。此时可利用数学公式直接根据总步数计算当前所在的边界、坐标和方向无需预存状态核心思路仍是“环上建模取模计算”。多指令联动优化若存在大量连续的step调用可直接累加所有num值减少多次累加的开销进一步提升效率当前代码已天然支持因total_steps是累加值。