今天刷题碰到个老朋友编号 2069中文名“模拟行走机器人 II”。第一眼看到“模拟行走机器人”我以为是 LeetCode 874 题那种在网格里自由走、绕障碍物的玩法结果读题读到一半发现完全不是一回事。这个版本把机器人限制在矩形边界上走像玩具火车围着轨道转圈而且单次移动步数最大能给到 10^9。如果你正在刷每日一题、想练练模拟题的优化思路或者被“大范围移动 实时查询方向”这种组合坑过这篇题解应该能帮你省不少时间。我先把思路、代码、坑全部记下来最后附上了我能想到的所有边角 case。1.2 暴力写法一眼就能看明白如果不管效率最直观的写法就是死循环每次先看下一步会不会撞墙不撞就走撞了就顺时针转向再走。for (int i 0; i num; i) { int nx x dx[dirIdx]; int ny y dy[dirIdx]; if (nx 0 || nx width || ny 0 || ny height) { dirIdx (dirIdx 1) % 4; nx x dx[dirIdx]; ny y dy[dirIdx]; } x nx; y ny; }这种写法在步数小的时候完全没问题代码 5 分钟写完。但问题出在数据范围上。题目里 num 最大能到 10^9这不是循环几次的问题是写完提交必 TLE 的程度。2.2 复杂度带来的双重压力假设机器人一次 move 最多走 10^9 步循环一千万次可能勉强能跑但一亿次、十亿次就完全没戏。更糟糕的是 move 方法会被多次调用如果每次调用都带一个很大的 num总步数可能到 10^9 乘以调用次数这个量级就算换成 C 也扛不住。那能不能对 num 做点文章关键观察是机器人被限制在矩形的边界上不管怎么走它永远不会进入内部区域。这意味着它的运动轨迹是固定的永远沿着矩形的四条边绕圈。这个性质非常重要因为绕圈是有周期性的一旦找到周期所有的大步数都可以压缩成“周期取模 余数模拟”。3.2 取模后状态真的能复原吗这里有一个很多新手会犹豫的点走完一圈回到原位方向一定还和原来一样吗答案是肯定的因为机器人在边界上行走时角点转向是固定顺序East 到 NorthNorth 到 WestWest 到 SouthSouth 到 East。走完一圈经历完整的 4 次转向方向自然回到初始方向。位置也一样因为周长 T 就是走完整个环的总步数。所以可以用一个取模操作把巨大步数缩小num % perimeter; if (num 0) return;num 是 perimeter 的整数倍时说明机器人走了完整的一圈或多圈最后位置和方向都和出发前完全一样直接返回就行。这个操作把 10^9 直接压到 40000 以内至少不会再因为单次步数过大而超时。3.3 从逐格走到按段跳每次 move 做到 O(1)取模后步数最多 39996在单次调用里逐格模拟是完全没问题的。但题目中 move 可能会被调用很多次比如 10^4 甚至 10^5 次每次取模后还有接近 40000 步总步数会到 4e9还是可能超时。所以要再进一步改成按段跳不数格子而是直接判断“当前方向上还能走多少步到下一个角点”然后一次性跨过这一段。这样每走完一段就转向一次最多转向 4 次就会回到起点。由于取模后剩余步数一定小于周长所以在这个过程中一定可以把余数步数消耗完不可能出现死循环。单次 move 的时间复杂度降为 O(1)这个方案才真正达到题目要求。4. 代码实现一份可以直接 AC 的 Java 解法4.1 方向数组与状态变量的选择我习惯用方向数组来管理四个方向这样坐标更新和转向都可以用索引操作比写四个 if 分支清爽很多。同时用一个字符串数组保存方向名getDir 直接返回字符串。核心状态变量包括当前位置 (x, y)、当前方向索引 dirIdx、矩形的宽高以及周长 perimeter。private static final int[][] DIRS {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; private static final String[] DIR_NAMES {East, North, West, South};注意方向数组的顺序必须和转向顺序一致East、North、West、South 循环。这样每次转向只需要dirIdx (dirIdx 1) % 4。4.2 move 方法的跳段实现move 方法的核心逻辑是取模、判断为 0 直接返回、然后进 while 循环按段跳。每一步先计算当前方向上还能走多远如果当前位置已经在角点上这个距离可能是 0那就先转向。如果剩余步数足够走到角点就直接走过去并结束如果不够就走到角点消耗掉对应步数转向后继续。public void move(int num) { if (num 0) return; num % perimeter; if (num 0) return; while (num 0) { int step 0; if (dirIdx 0) { // East step width - 1 - x; } else if (dirIdx 1) { // North step height - 1 - y; } else if (dirIdx 2) { // West step x; } else { // South step y; } if (step 0) { dirIdx (dirIdx 1) % 4; continue; } if (num step) { x DIRS[dirIdx][0] * num; y DIRS[dirIdx][1] * num; break; } num - step; x DIRS[dirIdx][0] * step; y DIRS[dirIdx][1] * step; dirIdx (dirIdx 1) % 4; } }这个写法有一个隐蔽点当num step时机器人正好停在某条边的中间或者角点上此时方向不要更新。为什么因为“转向”这个动作发生在到达角点之后、准备继续移动时。如果步数恰好耗尽在角点上按照题目对初始状态的定义机器人此时应该保持来时的方向。这一点非常重要很多错误答案就是在这个细节上翻的车。4.3 getPos、getDir 与构造方法构造方法里只需要初始化宽高、周长、起点和初始方向。起点 (0, 0)方向索引 0也就是 East。public Robot(int width, int height) { this.width width; this.height height; this.perimeter 2 * (width height - 2); this.x 0; this.y 0; this.dirIdx 0; } public int[] getPos() { return new int[]{x, y}; } public String getDir() { return DIR_NAMES[dirIdx]; }getPos 要求返回数组getDir 返回方向字符串。这里不需要额外处理“是否调用过 move”因为初始状态就是 East不移动时直接返回默认值就合法。move 里对 0 步的防御性返回也保证了不会有意外状态变更。5. 现场踩坑记录这些细节不处理必错5.1 角点上的方向更新时机前面提到过步数刚好耗尽在角点时不更新方向这一点需要重点强调。我自己第一次写的时候习惯“到达角点立刻转向”结果在简单例子上就错了。比如 width6、height3从 (0,0) 执行 move(5)刚好走到右上角 (5,0)。此时正确答案的方向应该是 East还是 North从官方对初始状态的定义反推机器人初始在 (0,0)方向 East(0,0) 本身就是一个角点。如果“到达角点立刻转向”成立机器人一开始就应该转向 North这显然和题目输入不符。所以正确理解是方向只有在角点并且需要继续走时才会更新停在角点不更新方向。代码中num step分支不更新 dirIdx正是为了符合这个语义。5.2 num % perimeter 0 时直接返回的坑取模后如果 num 变成 0说明移动步数是周长的整数倍此时位置和方向都恢复原样。这个结论本身没问题但如果你在取模后还继续执行跳段逻辑就可能出错因为跳段逻辑遇到 num0 不会进入循环所以其实问题不大。真正要注意的是不要在取模前做特殊处理。我见过有同学在取模前先判断num perimeter然后手动减去多个周长结果漏掉方向变化最后在宽高组合比较特殊的用例上出错。正确做法就是先取模然后让num 0时直接返回状态保持不变简单又安全。5.3 细长矩阵下的退化成线段问题当 width1 或 height1 时矩形边界退化成一条线段。此时周长公式依然成立但机器人会走到底、折返、再走到底、再折返循环往复。我的代码在 step0 时会先转向这恰好处理了线段端点的情况。比如 width1、height3初始在 (0,0)方向 East但 East 方向一步都走不了于是立刻转向 Northmove(2) 会走到 (0,2)。再 move(2)会先到 (0,0) 转向 East不到 (0,0) 后方向 South但 South 无路可走会继续转向 East然后从 (0,1) 再走这种用例不多但一旦边界条件没想清楚很容易写出死循环或者方向错误。我把几个高频问题整理成一个速查表刷题时直接对照问题触发场景错误做法正确做法步数刚好到达角点时耗尽更新方向为转向后方向保持当前方向因为转向是下一步动作num 是周长的整数倍手动减一个周长再继续走先取模num0 时直接返回width1 或 height1认为机器人无法移动直接返回正常跳段step0 时先转向再走move 被多次调用每次重新计算完整路径每次单独取模状态由全局坐标和方向记录5.4 测试用例驱动调试拿到这道题我建议先手算几个用例再写代码。第一个用例是 width3、height3周长 8。初始 (0,0) Eastmove(2) 到 (2,0) Eastmove(6) 应该回到 (0,0) East再 move(1) 到 (1,0) 还是到 (0,1)因为从 (0,0) East 走 1 步显然到 (1,0)但此时方向还是 East。这种小用例可以快速验证取模和方向逻辑。第二个用例是 width6、height3验证 move(4) 后再 move(4) 的方向。从 (0,0) East 走 4 步到 (4,0)方向 East再 move(4)先向东走 1 步到 (5,0)转向 North再走 3 步到 (5,3)不对height3 意味着 y 最大 2从 (5,0) North 走 2 步到 (5,2)剩余 1 步转向 West 走到 (4,2)。所以最终位置 (4,2)方向 West。这个用例能同时检验角点转向和跨段跳步。6. 从这道题延伸出去的通用技巧6.1 环形路径模拟的固定套路“模拟行走机器人 II”这类问题在 LeetCode 里不算少数共同特征是对象在固定轨道上循环运动步数可能很大查询可能频繁。通用的解法套路就是三步找周期、取模、按段跳。找周期通常看路径是不是一个闭环闭环的周长就是周期。取模把大数变小避免超时。按段跳则是在取模之后进一步把 O(周期) 压到 O(1)应对高频调用。比如一些环形队列、轮转数组、螺旋矩阵相关问题都能用这个思路做优化。核心就是意识到“循环路径上的状态具有周期性”一旦抓住周期大数就没有威胁了。6.2 和 874 题“模拟行走机器人”一起刷如果对模拟题感兴趣强烈建议把 874 题和这题放在一起刷。874 题是开放网格模拟有障碍物考察实时碰撞检测和方向控制本题是边界闭环模拟考察周期性和数学化简。两题名字相同思路却完全不同。合在一起刷你能直观感受到同一个主题下出题人如何通过不同约束考出完全不同的知识点。我自己刷完这两题最大的体会是模拟题不一定永远靠硬模拟先观察运动规律很多题一旦看出“环”的本质方案会简单很多。最后分享一个我实操中的小技巧写这类题时不要着急写 move 的完整跳段逻辑先把暴力模拟写对再用小数据用例验证方向规则最后再改成跳段版本。这样能把方向语义和优化逻辑分开调试出错时更容易定位。我第一次优化时直接写跳段结果方向在角点问题上来回错了好几次后来老老实实先跑暴力版对照才把逻辑理清楚。如果你也在刷这题希望这篇笔记能帮你绕过这些坑。