题目描述
思路解析动画文字版
记牢这套打法:方向查表变成坐标增量,每个起点都回到 startPos 从头走,走每一步之前先判下一格在不在网格里,出界就停、把已经走的步数记下来。下面把四个方向和增量对上号:L 列减一、R 列加一、U 行减一、D 行加一,然后一个起点一个起点地在网格上走给你看。
第 0 条开始 · 后缀 "RRDDLU"：换到起始下标 i=0 开始,机器人先回到起点坐标 (0,1),步数 t 清零。这一轮要执行的后缀是 "RRDDLU"。注意每换一个起始下标都是从起点坐标 (0,1) 重新出发,前面那轮走到哪跟这一轮没关系。
走 R(向右) · 到 (0,2)：第 0 条是 R,向右走。下一格是 (0,2),判一下:0 ≤ 0 < 3 且 0 ≤ 2 < 3,都成立,还在网格里,机器人走过去,t 加到 1。
走 R(向右) · 会出界,停：第 1 条是 R,向右走,下一格要到 (0,3),列号会变成 3,不满足 0 ≤ 列 < 3,越出网格了。机器人不走这一步、当场停下。这一轮从第 0 条开始成功走了 1 条,所以 answer[0]=1。
第 1 条开始 · 后缀 "RDDLU"：换到起始下标 i=1 开始,机器人先回到起点坐标 (0,1),步数 t 清零。这一轮要执行的后缀是 "RDDLU"。注意每换一个起始下标都是从起点坐标 (0,1) 重新出发,前面那轮走到哪跟这一轮没关系。
走 R(向右) · 到 (0,2)：第 1 条是 R,向右走。下一格是 (0,2),判一下:0 ≤ 0 < 3 且 0 ≤ 2 < 3,都成立,还在网格里,机器人走过去,t 加到 1。
走 D(向下) · 到 (1,2)：第 2 条是 D,向下走。下一格是 (1,2),判一下:0 ≤ 1 < 3 且 0 ≤ 2 < 3,都成立,还在网格里,机器人走过去,t 加到 2。
走 D(向下) · 到 (2,2)：第 3 条是 D,向下走。下一格是 (2,2),判一下:0 ≤ 2 < 3 且 0 ≤ 2 < 3,都成立,还在网格里,机器人走过去,t 加到 3。
走 L(向左) · 到 (2,1)：第 4 条是 L,向左走。下一格是 (2,1),判一下:0 ≤ 2 < 3 且 0 ≤ 1 < 3,都成立,还在网格里,机器人走过去,t 加到 4。
走 U(向上) · 到 (1,1)：第 5 条是 U,向上走。下一格是 (1,1),判一下:0 ≤ 1 < 3 且 0 ≤ 1 < 3,都成立,还在网格里,机器人走过去,t 加到 5。
后缀走完 · answer[1]=5：后缀 "RDDLU" 全部执行完了,一路都没出网格,机器人停在 (1,1)。从第 1 条开始,5 条指令全部走成功,answer[1]=5。
第 2 条开始 · 后缀 "DDLU"：换到起始下标 i=2 开始,机器人先回到起点坐标 (0,1),步数 t 清零。这一轮要执行的后缀是 "DDLU"。注意每换一个起始下标都是从起点坐标 (0,1) 重新出发,前面那轮走到哪跟这一轮没关系。
走 D(向下) · 到 (1,1)：第 2 条是 D,向下走。下一格是 (1,1),判一下:0 ≤ 1 < 3 且 0 ≤ 1 < 3,都成立,还在网格里,机器人走过去,t 加到 1。
走 D(向下) · 到 (2,1)：第 3 条是 D,向下走。下一格是 (2,1),判一下:0 ≤ 2 < 3 且 0 ≤ 1 < 3,都成立,还在网格里,机器人走过去,t 加到 2。
走 L(向左) · 到 (2,0)：第 4 条是 L,向左走。下一格是 (2,0),判一下:0 ≤ 2 < 3 且 0 ≤ 0 < 3,都成立,还在网格里,机器人走过去,t 加到 3。
走 U(向上) · 到 (1,0)：第 5 条是 U,向上走。下一格是 (1,0),判一下:0 ≤ 1 < 3 且 0 ≤ 0 < 3,都成立,还在网格里,机器人走过去,t 加到 4。
后缀走完 · answer[2]=4：后缀 "DDLU" 全部执行完了,一路都没出网格,机器人停在 (1,0)。从第 2 条开始,4 条指令全部走成功,answer[2]=4。
第 3 条开始 · 后缀 "DLU"：换到起始下标 i=3 开始,机器人先回到起点坐标 (0,1),步数 t 清零。这一轮要执行的后缀是 "DLU"。注意每换一个起始下标都是从起点坐标 (0,1) 重新出发,前面那轮走到哪跟这一轮没关系。
走 D(向下) · 到 (1,1)：第 3 条是 D,向下走。下一格是 (1,1),判一下:0 ≤ 1 < 3 且 0 ≤ 1 < 3,都成立,还在网格里,机器人走过去,t 加到 1。
走 L(向左) · 到 (1,0)：第 4 条是 L,向左走。下一格是 (1,0),判一下:0 ≤ 1 < 3 且 0 ≤ 0 < 3,都成立,还在网格里,机器人走过去,t 加到 2。
走 U(向上) · 到 (0,0)：第 5 条是 U,向上走。下一格是 (0,0),判一下:0 ≤ 0 < 3 且 0 ≤ 0 < 3,都成立,还在网格里,机器人走过去,t 加到 3。
后缀走完 · answer[3]=3：后缀 "DLU" 全部执行完了,一路都没出网格,机器人停在 (0,0)。从第 3 条开始,3 条指令全部走成功,answer[3]=3。
第 4 条开始 · 后缀 "LU"：换到起始下标 i=4 开始,机器人先回到起点坐标 (0,1),步数 t 清零。这一轮要执行的后缀是 "LU"。注意每换一个起始下标都是从起点坐标 (0,1) 重新出发,前面那轮走到哪跟这一轮没关系。
走 L(向左) · 到 (0,0)：第 4 条是 L,向左走。下一格是 (0,0),判一下:0 ≤ 0 < 3 且 0 ≤ 0 < 3,都成立,还在网格里,机器人走过去,t 加到 1。
走 U(向上) · 会出界,停：第 5 条是 U,向上走,下一格要到 (-1,0),行号会变成 -1,不满足 0 ≤ 行 < 3,越出网格了。机器人不走这一步、当场停下。这一轮从第 4 条开始成功走了 1 条,所以 answer[4]=1。
第 5 条开始 · 后缀 "U"：换到起始下标 i=5 开始,机器人先回到起点坐标 (0,1),步数 t 清零。这一轮要执行的后缀是 "U"。注意每换一个起始下标都是从起点坐标 (0,1) 重新出发,前面那轮走到哪跟这一轮没关系。
走 U(向上) · 会出界,停：第 5 条是 U,向上走,下一格要到 (-1,1),行号会变成 -1,不满足 0 ≤ 行 < 3,越出网格了。机器人不走这一步、当场停下。这一轮从第 5 条开始成功走了 0 条,所以 answer[5]=0。
六个起点各跑一遍 · 答案 [1,5,4,3,1,0]：六个起始下标各自回到起点坐标走了一遍,把每轮成功的步数按顺序排起来,就是答案 [1,5,4,3,1,0]。回看全程,套路就三句:方向查表变增量,每个起始下标都回到起点坐标重跑,走前判越界、出界即停数步数。要提醒一句:起始下标越靠后,剩余后缀的长度上限确实越短,但实际能走几步还要看路径是否提前出界,并不保证越来越少,本例第 1 条反而比第 0 条走得更远。
边界想清:n=1 时任何方向都出界全为 0、角落起步朝内走能走通、单条指令答案长度也是 1。
面试重点:可用前缀加倒扫优化到 O(m) 但本题暴力已够、方向查表省掉四个 if、四个越界条件缺一不可。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]: ans = [] m = len(s) mp = {"L": [0, -1], "R": [0, 1], "U": [-1, 0], "D": [1, 0]} for i in range(m): x, y = startPos t = 0 for j in range(i, m): a, b = mp[s[j]] if 0 <= x + a < n and 0 <= y + b < n: x, y, t = x + a, y + b, t + 1 else: break ans.append(t) return ans复杂度
- 时间：O(m²)，m 是指令串长度。外层枚举 m 个起点,内层从起点往后最多走到串尾,最坏是 m 步,两层相乘是 O(m 的平方)。每一步只做常数次坐标计算和一次越界判断。m 最大 500,平方约 25 万,暴力足够快
- 空间：O(1)，按额外占用的峰值算。只有一张固定四项的方向表和 x、y、t 几个变量,大小和输入规模无关,是常数。返回的答案数组是必须的输出、不计入额外空间
易错点
面试追问把动画讲成自己的话
追问这题能不能优化到比 O(m²) 更快?
追问为什么用哈希表存方向,而不是写四个 if 分支?
追问越界判断的四个条件能不能少写几个?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
银行中的激光束数量
LeetCode 2125 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题