LeetCode LCP 17. 速算机器人
目录
题目描述
题意分析
机器人有两个寄存器
x和y，初始值分别是 1 和 0。指令串s只由A、B两种字符组成：读到A时把x更新成2x + y，读到B时把y更新成2y + x。要求把整串指令执行完，返回x + y。
约束里最显眼的信号是
s的长度不超过 10，而且指令之间没有任何跳转、循环或撤销：第i条指令只依赖执行完前i-1条之后的寄存器值。这种"状态完全由前缀决定、且规模极小"的形态，说明不需要任何搜索或状态压缩，顺序推进两个整数就够了。
边界上要留意三点：
x的初值是 1 而不是 0，写错会让整条链路全为 0；每条指令只改一个寄存器，另一个保持不变；字符集只有A/B两种，所以else分支等价于B，不必再写第三个分支。数值范围方面，长度 10 时x + y只有 $2^{10} = 1024$，int 完全够用。
解法：按题意模拟
核心思路
最朴素的想法是照抄题面：准备两个变量，从左到右扫一遍指令串，遇到什么就改什么。这个想法在这题上没有瓶颈——指令数最多 10 条，扫一遍就是 10 次加法，已经是下界了，因此不需要做任何优化。
真正值得在面试里说出口的是这里的不变量。设执行完前
k条指令后寄存器为 $x_k, y_k$，那么无论第k+1条是A还是B：如果是A，新的和为 $(2x_k + y_k) + y_k = 2(x_k + y_k)$；如果是B，新的和为 $x_k + (2y_k + x_k) = 2(x_k + y_k)$。两条路径给出完全相同的和。于是有不变量：
\[x_k + y_k = 2^k \cdot (x_0 + y_0) = 2^k\]
也就是说答案只和指令串的长度有关，和每条指令具体是 A还是B毫无关系，最终结果恒为 $2^{s }$。模拟写法是这个不变量的直接展开，二者答案必然一致；面试里先给模拟保证正确，再把这个不变量说出来，就是加分点。
解题步骤
- 初始化
x = 1、y = 0。这是题目给定的初态。之所以不能图省事写成x = y = 0，是因为不变量 $x + y = 2^k$ 的基底就是 $x_0 + y_0 = 1$，初值一旦归零，后面所有的翻倍都作用在 0 上，答案恒为 0。
- 从左到右逐字符扫描
s。方向必须是从左到右，因为第i条指令的输入是执行完前i-1条之后的寄存器值，反向扫描会破坏这个依赖顺序，得到的是另一个完全不同的过程。
- 读到
A就执行x = 2 * x + y，否则执行y = 2 * y + x。关键在于每一步只更新一个寄存器，另一个原封不动地作为"旧值"参与运算。如果两个都在同一步里更新，就相当于把两条指令压在一起执行，语义完全变了。
扫描结束后返回 x + y。返回的是两个寄存器的和，不是其中某一个。这里也可以顺手用不变量自查：返回值应当恰好等于 $2^{s }$。
以
s = "AB"走一遍：初始x = 1, y = 0，此时 $x + y = 1 = 2^0$。读到第一个字符A，执行x = 2*1 + 0 = 2，y保持 0，此时x = 2, y = 0，和为 $2 = 2^1$，符合不变量。读到第二个字符B，执行y = 2*0 + 2 = 2，x保持 2，此时x = 2, y = 2，和为 $4 = 2^2$。扫描结束，返回2 + 2 = 4。
换一条指令串
s = "AA"再走一遍验证不变量：初始x = 1, y = 0；第一个A后x = 2, y = 0；第二个A后x = 2*2 + 0 = 4, y = 0；返回4 + 0 = 4。和"AB"的答案一致，正好印证了"答案与指令内容无关，只与长度有关"。
代码实现
class Solution {
public int calculate(String s) {
int x = 1;
int y = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == 'A') {
x = 2 * x + y;
} else {
y = 2 * y + x;
}
}
return x + y;
}
}
func calculate(s string) int {
x, y := 1, 0
for i := 0; i < len(s); i++ {
if s[i] == 'A' {
x = 2*x + y
} else {
y = 2*y + x
}
}
return x + y
}
复杂度分析
时间复杂度：$O( s )$。只对指令串做一次线性扫描，每个字符对应常数次加法与乘法，没有回溯也没有嵌套循环。 - 空间复杂度：$O(1)$。全程只有
x、y两个 int 变量和一个循环下标，与输入长度无关。
关键点总结
- 先找"两条分支的公共效果"，再决定要不要真的分情况。
A和B看似两种不同变换，但对 $x + y$ 这个聚合量的作用完全相同。遇到多分支状态机时，先问一句"有没有某个线性组合在所有分支下都同样变化"，往往能一眼看穿题目。- 不变量要写成等式而不是一句话。把结论落到 $x_k + y_k = 2^k$ 这种可验证的形式，才能拿它做自查和归纳证明；停留在"和会翻倍"的口头描述，很容易在推广到别的题时失效。
面试视角：先给能过的模拟，再给 $O(1)$ 的数学解。面试官出这题不是要看你会不会写 for 循环，而是看你能否从模拟里读出结构。稳妥的答法是先用 30 秒说清模拟并写出来，然后主动补一句"其实答案恒为 $2^{ s }$，因为每条指令都让 $x+y$ 翻倍"，把主动权拿回来。 - 规模极小的约束是"不必优化"的许可。
|s| ≤ 10明确告诉你朴素模拟稳过，此时纠结常数优化是浪费时间，把精力放在把不变量讲清楚上收益更高。- 状态更新的原子性要显式确认。每步只写一个寄存器、另一个读旧值，这是"顺序执行"语义的直接体现。凡是同时更新多个互相引用的变量时，都要停下来确认用的是不是同一时刻的快照。
易错点总结
- 错误写法：
int x = 0, y = 0;→ 用例s = "A"：x = 2*0 + 0 = 0，返回 0，而正确答案是 2。初值写错会让整条翻倍链塌成常数 0，且所有用例都错，反而不容易定位。- 错误写法：
int x = 0, y = 1;（把两个初值弄反） → 用例s = "A"：x = 2*0 + 1 = 1，返回1 + 1 = 2，恰好蒙对；但用例s = "AA"：第一步x = 1，第二步x = 2*1 + 1 = 3，返回 4，虽然也对——因为不变量对任何 $x_0+y_0=1$ 的初值都成立。真正会错的是s = ""之外的题面变体，一旦题目改成返回x而非x+y，这个错误立刻暴露，属于"用例碰巧掩盖"的高危写法。- 错误写法：
x = 2 * x + y; y = 2 * y + x;写在同一次迭代里，不加 if 分支 → 用例s = "A"：x变成 2 后y又被更新成2*0 + 2 = 2，返回 4，而正确答案是 2。这等于把一条指令当两条执行，长度为n的串会得到 $4^n$ 量级的结果。
错误写法： y = 2 * y + x里的x误用成刚更新过的值（先算x再在同一条B分支里引用） → 用例s = "BB"：正确过程是y = 2*0+1 = 1，再y = 2*1+1 = 3，返回 4；若中途污染了x，会得到x + y ≠ 4，直接违反 $x+y=2^{s }$，用不变量一算就能发现。 - 错误写法：
return x;或return y;→ 用例s = "AB"：正确答案是 4，但return x得到 2、return y也得到 2。题目要的是两个寄存器之和，只返回单个寄存器会在几乎所有非平凡用例上偏小。- 错误写法：
for (int i = 1; i < s.length(); i++)（下标从 1 开始） → 用例s = "AB"：漏掉首字符A，只执行B，得到x = 1, y = 2*0+1 = 1，返回 2 而非 4。字符串下标从 0 起，循环条件写成i < s.length()才恰好覆盖全部字符。- 错误写法：
if (c == 'A') {...} else if (c == 'B') {...}但漏写 else 分支后又在外层做了别的处理 → 用例s = "AB"本身不会错，但如果误把判断写成if (c == 'B')在前、else当作A，逻辑就整体反了："AB"会先更新y再更新x，得到y = 1, x = 2*1+1 = 3，返回 4——又一次被不变量"救"回来，但过程完全错误。判断字符时务必和题面逐字对齐。- 错误写法：用
s.charAt(i) == "A"（Java 里拿 char 和 String 比） → 直接编译失败；换成equals又要先String.valueOf，白白引入装箱开销。Java 中单字符比较应写== 'A'。- 错误写法：Go 里写
for _, c := range s后用c == 'A'但把c当成 byte 处理下标 → 本题字符集是 ASCII 不会出错，但range string产生的是 rune 和字节偏移，一旦题面换成含多字节字符的串，i就不再是"第几个字符"。按下标s[i]遍历语义更直白。- 错误写法：用
Math.pow(2, s.length())直接返回浮点结果 → 用例s长度为 10 时得到1024.0，强转 int 虽然对，但浮点在更长的串上会丢精度，且面试官会追问"为什么敢用浮点算整数幂"。要么老实模拟，要么用位移1 << s.length()。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 874. 模拟行走机器人 | 中等 | 状态里多了朝向和障碍集合，需要哈希去重而非纯算术递推 |
| 1041. 困于环中的机器人 | 中等 | 靠"一轮指令后朝向是否复位"做周期性判定，而不是直接算终值 |
| 面试题 16.22. 兰顿蚂蚁 | 中等 | 网格无限大且格子颜色会反复翻转，必须动态维护包围盒 |
| 面试题 08.02. 迷路的机器人 | 中等 | 从确定性模拟升级成带回溯与剪枝的路径搜索 |