算法刷题系列（一）：模拟法——从题意到状态更新
算法刷题系列（一）：模拟法——从题意到状态更新
模拟法通常是最直接的算法：题目给出一组规则，我们按规则一步一步执行，并记录当前状态。它不一定需要复杂的数据结构，但很考验建模是否完整——变量代表什么、操作顺序是什么、边界如何处理，都要先说清楚。
这一篇从一个自创的机器人指令例子开始，演示如何把自然语言转换成状态更新，并分别用 Java 和 Python 实现。
一、什么时候考虑模拟？
题目如果描述了一个过程，并要求给出执行后的结果，通常可以先问：
- 当前状态是什么？ 例如位置、方向、分数、库存或棋盘。
- 有哪些操作？ 每个操作如何改变状态？
- 操作按什么顺序发生？ 顺序是否会影响结果？
- 何时结束，输出什么？ 需要输出最终状态，还是过程中第一次满足条件的时刻？
如果能用有限个变量完整表示当前状态，而且每个操作都能直接计算，就可以先尝试模拟。
二、例子：执行机器人指令
一个机器人从平面坐标 (0, 0) 出发，初始朝北。它会收到一串指令：
F：向当前朝向前进一步；L：向左转 90 度；R：向右转 90 度。
指令串为 FFRFLF，求最后的位置和朝向。
1. 定义状态
用三个变量描述机器人：
x：横坐标；y：纵坐标；direction：朝向编号。
把方向编号约定为：
| 编号 | 方向 | 坐标变化 |
|---|---|---|
| 0 | 北 | (0, 1) |
| 1 | 东 | (1, 0) |
| 2 | 南 | (0, -1) |
| 3 | 西 | (-1, 0) |
方向变化可以用模 4 运算：
- 向右：
(direction + 1) % 4 - 向左：
(direction + 3) % 4
向左不是简单地减 1 后取模，因为某些语言对负数取模的结果不同；加 3 再取模能统一得到非负方向编号。
2. 手动走一遍
| 指令 | 位置变化后 | 朝向 |
|---|---|---|
| 初始 | (0, 0) | 北 |
F | (0, 1) | 北 |
F | (0, 2) | 北 |
R | (0, 2) | 东 |
F | (1, 2) | 东 |
L | (1, 2) | 北 |
F | (1, 3) | 北 |
最终位置是 (1, 3)，朝北。
三、算法步骤
- 初始化位置为
(0, 0)，方向为北。 - 从左到右读取每条指令。
- 如果是
F，按当前方向对应的坐标增量更新位置。 - 如果是
L或R，只更新方向编号。 - 所有指令执行完后返回最终状态。
每条指令只处理一次，因此时间复杂度是 O(n)，其中 n 是指令数。除输入外只使用常数个变量，额外空间复杂度是 O(1)。
四、Java 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class RobotSimulation {
// direction: 0 = north, 1 = east, 2 = south, 3 = west
public static int[] execute(String commands) {
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
int x = 0;
int y = 0;
int direction = 0;
for (char command : commands.toCharArray()) {
if (command == 'F') {
x += dx[direction];
y += dy[direction];
} else if (command == 'R') {
direction = (direction + 1) % 4;
} else if (command == 'L') {
direction = (direction + 3) % 4;
} else {
throw new IllegalArgumentException(
"Unsupported command: " + command
);
}
}
return new int[] {x, y, direction};
}
}
execute("FFRFLF") 返回 {1, 3, 0}，其中方向编号 0 表示北。
这里显式处理了未知指令，而不是静默忽略。若题目保证输入合法，可以按题目约束简化；若输入来自真实用户或外部系统，则应保留校验。
五、Python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def execute(commands: str) -> tuple[int, int, int]:
# direction: 0 = north, 1 = east, 2 = south, 3 = west
dx = (0, 1, 0, -1)
dy = (1, 0, -1, 0)
x = 0
y = 0
direction = 0
for command in commands:
if command == "F":
x += dx[direction]
y += dy[direction]
elif command == "R":
direction = (direction + 1) % 4
elif command == "L":
direction = (direction + 3) % 4
else:
raise ValueError(f"Unsupported command: {command}")
return x, y, direction
execute("FFRFLF") 返回 (1, 3, 0)。
六、边界情况与测试
空指令
输入为空字符串时，机器人不移动也不转向，结果应为 (0, 0, 0)。
只转向
输入 LLL 时，位置保持 (0, 0)，方向变为西，也就是编号 3。
连续转满一圈
输入 RRRR 后方向应回到北。这个用例可以检查模运算和方向编号约定是否一致。
未知指令
输入中出现未定义字符时，示例实现会报错。若题意规定所有字符都合法，则该分支不会触发；若输入约束不明确，应先确认题目要求。
最简单的验证方式是用纸笔按相同规则走一遍短指令，再比较程序输出。模拟题往往错误在状态更新顺序，而不在循环语法。
七、模拟题常见错误
- 状态定义不完整：例如记录了位置，却忘记记录朝向。
- 方向顺序不统一：方向数组顺序和转向公式必须采用同一约定。
- 边界更新混乱：左转、右转的模运算写错，或负数取模行为与预期不同。
- 只看最终样例：中间状态不容易观察时，先构造只有一两步的小测试。
- 把模拟当成低效算法：如果题目要求逐项执行
n条指令，O(n)往往已经是最优量级；需要优化的是不必要的重复计算，而不是省略必需步骤。
八、如何从模拟继续优化
模拟是建立正确基线的好方法。写完后可以继续追问：
- 每一步是否都必须逐个执行？能否把一段重复操作合并？
- 是否可以用计数或哈希表减少重复查找？
- 是否有连续区间可以用滑动窗口或前缀信息处理？
- 状态空间很大时，能否用搜索、动态规划或数学规律跳过部分状态？
这些问题会自然连接到本系列后面的哈希表、双指针、前缀和、搜索和动态规划。不要为了“用高级算法”而优化；只有在数据规模或重复工作确实构成瓶颈时，才替换简单模拟。
小结
模拟法的核心是把题意转成状态和操作：先定义状态变量，再逐条应用规则，最后检查边界和结果。机器人例子中，坐标和朝向足以表示完整状态；每条指令只需常数时间处理，因此总复杂度为 O(n)。
接下来适合学习哈希表：当模拟过程中频繁查找“某个值是否出现过、出现了几次”时，哈希结构往往能把反复扫描转成近似常数时间查询。