LeetCode 2120中等数组 · 哈希
执行所有后缀指令 图解题解
这道题到底在问什么
给你整数 n 和起点 startPos=[start_row, start_col],以及长度为 m 的指令串 s。机器人从第 i 条指令开始逐条执行,当「下一条指令会走出网格」或「指令已执行完」时停止。返回长度为 m 的数组 answer,answer[i] 是从第 i 条开始能执行的指令条数。坐标满足 0 ≤ 行 < n 且 0 ≤ 列 < n 才算在网格内。
- 输入
- n=3, startPos=[0,1], s="RRDDLU"
- 输出
- [1,5,4,3,1,0]
- 输入
- n=2, startPos=[1,1], s="LURD"
- 输出
- [4,1,0,0]
最优解：一步一步想明白
- 3记牢这套打法:方向查表变成坐标增量,每个起点都回到 startPos 从头走,走每一步之前先判下一格在不在网格里,出界就停、把已经走的步数记下来。下面把四个方向和增量对上号:L 列减一、R 列加一、U 行减一、D 行加一,然后一个起点一个起点地在网格上走给你看。
- 4起点就位 (0,1),t=0换到起始下标 i=0 开始,机器人先回到起点坐标 (0,1),步数 t 清零。这一轮要执行的后缀是 "RRDDLU"。注意每换一个起始下标都是从起点坐标 (0,1) 重新出发,前面那轮走到哪跟这一轮没关系。
- 5向右到 (0,2),t=1第 0 条是 R,向右走。下一格是 (0,2),判一下:0 ≤ 0 < 3 且 0 ≤ 2 < 3,都成立,还在网格里,机器人走过去,t 加到 1。
- 6出界停,answer[0]=1第 1 条是 R,向右走,下一格要到 (0,3),列号会变成 3,不满足 0 ≤ 列 < 3,越出网格了。机器人不走这一步、当场停下。这一轮从第 0 条开始成功走了 1 条,所以 answer[0]=1。
- 7起点就位 (0,1),t=0换到起始下标 i=1 开始,机器人先回到起点坐标 (0,1),步数 t 清零。这一轮要执行的后缀是 "RDDLU"。注意每换一个起始下标都是从起点坐标 (0,1) 重新出发,前面那轮走到哪跟这一轮没关系。
- 8向右到 (0,2),t=1第 1 条是 R,向右走。下一格是 (0,2),判一下:0 ≤ 0 < 3 且 0 ≤ 2 < 3,都成立,还在网格里,机器人走过去,t 加到 1。
- 9向下到 (1,2),t=2第 2 条是 D,向下走。下一格是 (1,2),判一下:0 ≤ 1 < 3 且 0 ≤ 2 < 3,都成立,还在网格里,机器人走过去,t 加到 2。
- 10向下到 (2,2),t=3第 3 条是 D,向下走。下一格是 (2,2),判一下:0 ≤ 2 < 3 且 0 ≤ 2 < 3,都成立,还在网格里,机器人走过去,t 加到 3。
- 11向左到 (2,1),t=4第 4 条是 L,向左走。下一格是 (2,1),判一下:0 ≤ 2 < 3 且 0 ≤ 1 < 3,都成立,还在网格里,机器人走过去,t 加到 4。
- 12向上到 (1,1),t=5第 5 条是 U,向上走。下一格是 (1,1),判一下:0 ≤ 1 < 3 且 0 ≤ 1 < 3,都成立,还在网格里,机器人走过去,t 加到 5。
- 13指令走完,answer[1]=5后缀 "RDDLU" 全部执行完了,一路都没出网格,机器人停在 (1,1)。从第 1 条开始,5 条指令全部走成功,answer[1]=5。
- 14起点就位 (0,1),t=0换到起始下标 i=2 开始,机器人先回到起点坐标 (0,1),步数 t 清零。这一轮要执行的后缀是 "DDLU"。注意每换一个起始下标都是从起点坐标 (0,1) 重新出发,前面那轮走到哪跟这一轮没关系。
- 15向下到 (1,1),t=1第 2 条是 D,向下走。下一格是 (1,1),判一下:0 ≤ 1 < 3 且 0 ≤ 1 < 3,都成立,还在网格里,机器人走过去,t 加到 1。
- 16向下到 (2,1),t=2第 3 条是 D,向下走。下一格是 (2,1),判一下:0 ≤ 2 < 3 且 0 ≤ 1 < 3,都成立,还在网格里,机器人走过去,t 加到 2。
- 17向左到 (2,0),t=3第 4 条是 L,向左走。下一格是 (2,0),判一下:0 ≤ 2 < 3 且 0 ≤ 0 < 3,都成立,还在网格里,机器人走过去,t 加到 3。
- 18向上到 (1,0),t=4第 5 条是 U,向上走。下一格是 (1,0),判一下:0 ≤ 1 < 3 且 0 ≤ 0 < 3,都成立,还在网格里,机器人走过去,t 加到 4。
- 19指令走完,answer[2]=4后缀 "DDLU" 全部执行完了,一路都没出网格,机器人停在 (1,0)。从第 2 条开始,4 条指令全部走成功,answer[2]=4。
- 20起点就位 (0,1),t=0换到起始下标 i=3 开始,机器人先回到起点坐标 (0,1),步数 t 清零。这一轮要执行的后缀是 "DLU"。注意每换一个起始下标都是从起点坐标 (0,1) 重新出发,前面那轮走到哪跟这一轮没关系。
- 21向下到 (1,1),t=1第 3 条是 D,向下走。下一格是 (1,1),判一下:0 ≤ 1 < 3 且 0 ≤ 1 < 3,都成立,还在网格里,机器人走过去,t 加到 1。
- 22向左到 (1,0),t=2第 4 条是 L,向左走。下一格是 (1,0),判一下:0 ≤ 1 < 3 且 0 ≤ 0 < 3,都成立,还在网格里,机器人走过去,t 加到 2。
- 23向上到 (0,0),t=3第 5 条是 U,向上走。下一格是 (0,0),判一下:0 ≤ 0 < 3 且 0 ≤ 0 < 3,都成立,还在网格里,机器人走过去,t 加到 3。
- 24指令走完,answer[3]=3后缀 "DLU" 全部执行完了,一路都没出网格,机器人停在 (0,0)。从第 3 条开始,3 条指令全部走成功,answer[3]=3。
- 25起点就位 (0,1),t=0换到起始下标 i=4 开始,机器人先回到起点坐标 (0,1),步数 t 清零。这一轮要执行的后缀是 "LU"。注意每换一个起始下标都是从起点坐标 (0,1) 重新出发,前面那轮走到哪跟这一轮没关系。
- 26向左到 (0,0),t=1第 4 条是 L,向左走。下一格是 (0,0),判一下:0 ≤ 0 < 3 且 0 ≤ 0 < 3,都成立,还在网格里,机器人走过去,t 加到 1。
- 27出界停,answer[4]=1第 5 条是 U,向上走,下一格要到 (-1,0),行号会变成 -1,不满足 0 ≤ 行 < 3,越出网格了。机器人不走这一步、当场停下。这一轮从第 4 条开始成功走了 1 条,所以 answer[4]=1。
- 28起点就位 (0,1),t=0换到起始下标 i=5 开始,机器人先回到起点坐标 (0,1),步数 t 清零。这一轮要执行的后缀是 "U"。注意每换一个起始下标都是从起点坐标 (0,1) 重新出发,前面那轮走到哪跟这一轮没关系。
- 29出界停,answer[5]=0第 5 条是 U,向上走,下一格要到 (-1,1),行号会变成 -1,不满足 0 ≤ 行 < 3,越出网格了。机器人不走这一步、当场停下。这一轮从第 5 条开始成功走了 0 条,所以 answer[5]=0。
- 30答案 [1,5,4,3,1,0]六个起始下标各自回到起点坐标走了一遍,把每轮成功的步数按顺序排起来,就是答案 [1,5,4,3,1,0]。回看全程,套路就三句:方向查表变增量,每个起始下标都回到起点坐标重跑,走前判越界、出界即停数步数。要提醒一句:起始下标越靠后,剩余后缀的长度上限确实越短,但实际能走几步还要看路径是否提前出界,并不保证越来越少,本例第 1 条反而比第 0 条走得更远。
⚠️ 容易写错的地方
✗ 错：换起点时接着上一轮的位置走
✓ 对：每个起点都要回到 startPos 重新走
第 i 条的答案是「独立从起点出发」的结果,复用上一轮的落点会把轨迹算错
✗ 错：先移动再判断在不在网格里
✓ 对：走每一步之前先算下一格坐标再判越界
一旦先走出去再回退容易漏判、还可能用到越界坐标,规范做法是走之前就拦住
✗ 错：把行和列搞反
✓ 对：U、D 改的是行,L、R 改的是列
startPos 是 [行, 列],U 向上是行减一、L 向左是列减一,方向和行列对错位答案就全错
✗ 错：边界写成 0 ≤ 坐标 ≤ n
✓ 对：必须是 0 ≤ 坐标 < n
网格下标是 0 到 n 减一,坐标等于 n 已经出界,右边界要用严格小于 n
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> executeInstructions(int n, vector<int>& startPos, string s) {
int m = s.size();
vector<int> ans(m);
unordered_map<char, vector<int>> mp;
mp['L'] = {0, -1};
mp['R'] = {0, 1};
mp['U'] = {-1, 0};
mp['D'] = {1, 0};
for (int i = 0; i < m; ++i) {
int x = startPos[0], y = startPos[1];
int t = 0;
for (int j = i; j < m; ++j) {
int a = mp[s[j]][0], b = mp[s[j]][1];
if (0 <= x + a && x + a < n && 0 <= y + b && y + b < n) {
x += a;
y += b;
++t;
} else
break;
}
ans[i] = t;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int[] executeInstructions(int n, int[] startPos, String s) {
int m = s.length();
int[] ans = new int[m];
Map<Character, int[]> mp = new HashMap<>(4);
mp.put('L', new int[] {0, -1});
mp.put('R', new int[] {0, 1});
mp.put('U', new int[] {-1, 0});
mp.put('D', new int[] {1, 0});
for (int i = 0; i < m; ++i) {
int x = startPos[0], y = startPos[1];
int t = 0;
for (int j = i; j < m; ++j) {
char c = s.charAt(j);
int a = mp.get(c)[0], b = mp.get(c)[1];
if (0 <= x + a && x + a < n && 0 <= y + b && y + b < n) {
x += a;
y += b;
++t;
} else {
break;
}
}
ans[i] = t;
}
return ans;
}
}复杂度
时间
O(m²)
m 是指令串长度。外层枚举 m 个起点,内层从起点往后最多走到串尾,最坏是 m 步,两层相乘是 O(m 的平方)。每一步只做常数次坐标计算和一次越界判断。m 最大 500,平方约 25 万,暴力足够快
空间
O(1)
按额外占用的峰值算。只有一张固定四项的方向表和 x、y、t 几个变量,大小和输入规模无关,是常数。返回的答案数组是必须的输出、不计入额外空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 执行所有后缀指令 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题能不能优化到比 O(m²) 更快?+
可以做到 O(m)。核心观察是:机器人从某个起点走出去,一定是横坐标先撞到左右某条边界、或纵坐标先撞到上下某条边界。可以把行方向的位移和列方向的位移各做一遍前缀,再倒着扫,借助两个哈希表记录「每个位移值最近一次出现的位置」,就能对每个起点 O(1) 算出它在行或列上第一次越界的步数,取较小者即可。不过本题 m 最多 500,平方也才 25 万,暴力已经绰绰有余,面试里先给暴力、能说清优化思路即可。
为什么用哈希表存方向,而不是写四个 if 分支?+
把 L、R、U、D 直接映射成 [行增量, 列增量],走的时候一句「取出增量、加到当前坐标」就完事,不用四个 if 各写一遍越界判断,代码短、也不容易在某个分支里写错符号。这是处理「上下左右四方向移动」这类网格题的通用技巧,后面很多矩阵搜索题都用得上。
越界判断的四个条件能不能少写几个?+
不能省。二维网格要同时保证行在 [0,n) 且列在 [0,n),所以行的下界、行的上界、列的下界、列的上界四个条件缺一不可。少判一个方向,机器人就可能从那一侧溜出网格还被当成合法,答案立刻出错。写成 0 ≤ 行 < n 且 0 ≤ 列 < n 两组区间判断最清楚。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 执行所有后缀指令 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。