LeetCode 2069 模拟机器人II：批量跳步与边界处理全解析

做了这么多年算法题LeetCode 2069 模拟行走机器人 II 属于那种“看起来就是简单模拟真动手写却处处是坑”的题。很多人的第一反应是维护一个坐标和方向然后一步步走结果一看到num的范围就傻眼了步数大到离谱直接遍历必然超时。这篇内容我就以实际解题过程的视角把这道题从题意拆解、核心优化思路到最终可运行代码和踩坑点完整捋一遍尤其会讲清楚为什么“批量跳步”是这类题的标准解法。适合正在刷题准备面试、或者想系统掌握模拟题优化套路的朋友阅读。1. 题目到底在考什么1.1 题目描述与核心行为题目给了一个width x height的矩形网格机器人初始位置在(0, 0)初始朝向是East。注意这里的坐标我习惯用x表示列、y表示行(0, 0)就是左上角。网格外围一圈是机器人的活动范围它永远贴着最外圈走不会进入内部格子。机器人的命令有两种。第一种是step(num)让它尝试前进num步第二种是turnLeft()和turnRight()原地转向。关键在于step的执行规则每一步移动之前如果前方越界了就右转一次然后再走一步。这个“走一步前检查越界”的细节非常像真实机器人在地图边缘自动纠正方向而不是整段先转好再走。举个例子假设width 3, height 3机器人在(0, 0)面朝West前方越界所以右转成North如果North也越界还会继续右转直到找到一个不越界的方向再前进。这套规则会让机器人始终贴着矩形边界绕圈但方向不一定永远是顺时针切线方向这给优化带来了不少麻烦。1.2 为什么不能一格格模拟我第一次看到这题时差点直接写一个while num 0的循环每次走一步并判断是否越界、是否需要右转。但很快发现width、height以及单次num都可能达到10^9级别一步一循环的复杂度是O(num)即使在赛题里给了充足时间这种实现也很容易在某个极端用例上超时。更麻烦的是step命令可以连续调用很多次如果每次都从头一步步推累计下来的代价完全不可接受。所以核心诉求就很明确单次step不能依赖步数大小最好能做到常数时间或极小的常数次数完成。这种“步数巨大但移动路径有规律”的模拟题一般的思路就是寻找路径的结构把连续直线行走压缩成批量计算。矩形边界本身就是一条首尾相接的闭合折线机器人的运动轨迹天然被限制在这条折线上所以下一步的关键是怎么把“一段一段的直线运动”抽象出来。1.3 这题和普通机器人模拟的差异很多机器人模拟题是开放二维平面机器人可以自由走格子那种题一般靠 BFS 或者简单坐标累加。但 2069 的约束完全不同机器人永远被限制在最外圈也就是说它其实在一个“一维环形路径”上运动只不过这个一维路径被折叠成了矩形。这个认知很重要。如果你没有意识到路径是一维的就会去维护一个二维visited数组或者每次都判断四个方向是否越界代码会非常笨重。反过来一旦明确了活动范围就是矩形边界就可以把整条边界看成若干段直线每次在当前方向上尽量往前走走到头再转向。这样单次step只需要处理几次“直线段”和num的具体大小无关。2. 核心思路批量跳过直线段2.1 把矩形边界拆成 4 条线段矩形外圈本质上就是四条线段。假设网格从左到右是x从0到width-1从上到下是y从0到height-1那么四条线段分别是上边界y 0x从0到width-1行走方向是East右边界x width-1y从0到height-1行走方向是South下边界y height-1x从width-1到0行走方向是West左边界x 0y从height-1到0行走方向是North这里我采用“右转顺序”为East - South - West - North和屏幕上顺时针绕圈一致。如果你用数学坐标把North放上面右转顺序又会不同所以写代码前最好把坐标轴和方向顺序统一写在纸上否则很容易绕晕。在任意状态下机器人当前方向可能落在某条线段上也可能因为turnLeft/turnRight指向其他方向。但不管怎样它往当前方向走时最多只能走到这条线段尽头也就是矩形拐角。所以我可以算出“在当前方向上还能走多少步”然后一次跳完。2.2 当前方向最多能走多少步这里我把四个方向分别计算当前方向是East也就是列增加最多能走到x width - 1所以还能走width - 1 - x步。当前方向是South也就是行增加最多能走到y height - 1所以还能走height - 1 - y步。当前方向是West也就是列减少最多能走到x 0所以还能走x步。当前方向是North也就是行减少最多能走到y 0所以还能走y步。如果某个方向上可走的can等于 0说明机器人正站在这条线段的尽头再往前就出界了。按照题目的规则它必须先右转然后继续检查。这个“右转”操作并不会消耗步数但它会导致方向索引加一。真正走的时候我一次最多走min(num, can)步然后更新坐标并消耗对应的num。一段走完之后如果num还没耗尽说明已经走到拐角下一轮循环会先右转再继续。2.3 复杂度为什么是常数级很多读者可能会担心num可以到10^9如果每段走不了几步会不会循环很多次实际上不会。因为每当can 0时都会一次性走完当前方向上的可走距离只有走到拐角才会转向。沿着矩形边界绕一圈最多经历四次“走到头、转向”。也就是说即使初始方向比较奇怪最多也就是先反向走到某一个拐角再沿着闭合边界绕回来整体循环次数是常数级别可以看作 O(1)。这里顺便提醒一个细节有些题解会提到先对周长取模公式是perimeter 2 * (width height - 2)理由是一整圈后状态会复原。这个方法本身没毛病但如果机器人的当前方向并不是边界切线方向取模后依然要靠分段跳步来走并不能直接由取模结果算出最终位置。所以我的实现里干脆不依赖取模直接用 while 循环跳线段更通用也更不容易出错。3. 代码实现与边界处理3.1 状态设计与数据结构我选择用四个字段维护状态当前列x、当前行y、方向索引d、方向数组。方向数组按右转顺序排好class Robot: def __init__(self, width: int, height: int): self.w width self.h height self.x 0 # 列 self.y 0 # 行 self.d 0 # 右转顺序: East - South - West - North self.dx [1, 0, -1, 0] # 列方向变化 self.dy [0, 1, 0, -1] # 行方向变化 self.name [East, South, West, North]这里East是(dx1, dy0)表示列加一South是(dx0, dy1)表示行加一West是(dx-1, dy0)North是(dx0, dy-1)。这样从East往右转一次就变成South完全符合题目“越界就右转”的直觉。getPos和getDir就很好写了def getPos(self): return [self.x, self.y] def getDir(self): return self.name[self.d]需要说明如果题目要求的返回顺序是[y, x]把getPos里两个值换一下就行核心逻辑不变。3.2 step 函数完整实现step的核心就是循环处理“当前方向能走多少步”。完整代码如下def step(self, num: int) - None: while num 0: if self.d 0: # East can self.w - 1 - self.x if can 0: self.d 1 continue move min(num, can) self.x move num - move elif self.d 1: # South can self.h - 1 - self.y if can 0: self.d 2 continue move min(num, can) self.y move num - move elif self.d 2: # West can self.x if can 0: self.d 3 continue move min(num, can) self.x - move num - move else: # North can self.y if can 0: self.d 0 continue move min(num, can) self.y - move num - move这个版本的逻辑非常直白先看当前方向还能走多远如果走不了就右转否则一次性跳过去。可能有人会问为什么不把四个方向的can计算抽象成数组操作那样更优雅。确实可以比如通过判断dx和dy的正负来统一计算但面试时这种直白写法反而是最不容易出错的尤其是在时间紧张的情况下少一点花哨多一点确定性。3.3 边界情况与特判width 1或height 1时机器人只能在一条线上来回移动。这个解法能正确处理吗能。举个例子width 1, height 3初始在(0, 0)面朝East。此时East方向能走0步因为width - 1 - x 0于是右转成South。如果num还有剩余再走South方向直到下边界然后右转West再右转North整个过程会自动沿着这条“退化矩形”往返。只要不用固定思维觉得边界必须是四条线段这个循环在退化情形下依然正确。另一种边界情况是机器人初始方向经过turnLeft或turnRight后变成非切线方向。比如初始在(0, 0)先turnLeft()面朝North再执行step(1)。此时North方向can 0所以右转成East再走 1 步到(1, 0)最终方向是East。这个行为和真实规则完全一致既然向上出界就先转向再走而不是直接报错或原地不动。3.4 一个容易忽略的坐标混淆点我在写第一版时曾经把方向数组定义为East, North, West, South因为脑子里默认“向上是北、顺时针右转北在东的旁边”。结果走到右下角时机器人本来应该沿着右边界继续走却被算成转向后原路返回调试了很久才发现是坐标轴假设不一致。所以这里再强调一次如果用屏幕坐标也就是行y向下增大、列x向右增大那么右上角向右转一定是朝下走也就是South。如果用的是数学坐标行向上增大那右转顺序又会变。代码本身没有对错关键是要和你的坐标轴定义自洽。4. 踩坑记录与同类问题扩展4.1 三个容易翻车的细节第一个坑是方向顺序。很多人会在turnRight时写成索引减一结果整个绕圈方向变成逆时针。最好的检查方法是手动模拟一个width3, height3的简单矩形走一圈看看路径是否按预期绕边界。第二个坑是getPos的返回顺序。题目样例里给的位置可能是[x, y]但很多人内部用row, col存储最后忘了转换导致连续几个用例输出顺序颠倒。这类问题不是算法不会而是细节没对齐非常可惜。第三个坑是过度依赖取模。周长取模本身是正确思路的组成部分但前提是机器人方向始终是边界切线方向。如果题目连turnLeft/turnRight都能随时调用那么方向可能指向任何一边这时直接num % perimeter再继续分段跳步也不能说错但并不能简化循环反而增加了理解成本。我建议直接回归“每段直线批处理”的本源。4.2 从这题抽象出来的批量跳跃思想这类“步数巨大、路径可分段”的题核心思想是不要每一步都遍历而是找到不可分割的“大步长”。常见套路包括在数组中按固定步长移动优先用取模确定周期。在棋盘/网格上模拟优先按“直到边界或障碍”切分直线段。在有环路径上累计移动优先计算环的周长和偏移。这种思想有点像把一段长视频按镜头切分成关键帧你不需要看每一帧只需要知道每个镜头的起点和长度就能快速跳到任意时间点。2069 的四条边界线段就是四个镜头。4.3 如果题目改成“统计走过的不同格子”最后做个扩展。如果面试官问你能否让机器人走完10^9步后统计它一共经过了多少个不同的格子这时候问题就完全变了不能只记录终点必须记录整段路径的覆盖范围。但因为路径始终在边界上统计每个方向线段经过的区间再用排序或差分合并重复覆盖就能在常数空间内算出来。这也是从“单点定位”升级到“区间覆盖”的常见演变。我自己最早做这题时就因为方向顺序写反浪费了大把时间。后来养成了一个习惯凡是带方向模拟的题先花十秒在草稿纸上画一下坐标轴和右转顺序。这个习惯帮我避免了很多低级错误。希望这篇内容也能让你少踩一次坑。