LeetCode LCP 17. 速算机器人
题目描述
题意分析
初始
x = 1、y = 0，按字符串从左到右执行指令：A只更新x = 2 * x + y，B只更新y = 2 * y + x。最终返回两个变量的和，而不是某一个变量。
解法：按题意模拟
核心思路
[!blue]
用
x、y保存执行完当前指令前缀后的两个数。每次读取下一条指令，只套用它对应的一条公式，另一变量保持不变。右侧表达式使用更新前的值，因此一个条件分支中的一次赋值就能完成操作，不需要同时更新两个变量。初值与题意一致，而每一步又严格执行当前指令的定义，所以每轮之后，变量都等于相应指令前缀执行后的真实状态。遍历结束时返回
x + y，就是全部指令的结果。总和还有一个不变量：执行
A后为(2 * x + y) + y = 2 * (x + y)；执行B后为x + (2 * y + x) = 2 * (x + y)。两种指令都会让总和翻倍，从初始和1出发，执行t条指令后的和就是 $2^t$。具体顺序可能改变x、y各自的值，但不改变最终总和。
解题步骤
- 初始化 x=1、y=0。
- 依次读取指令，只更新它指定的变量。
- 完成后返回两者之和。
题目保证字符只有
A、B，所以代码的另一个分支可以直接处理B。空字符串不执行任何更新，返回初始和1；字符串长度最多为10，总和最多为1024，普通整数即可保存。
代码实现
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(\lvert s\rvert+1)$，当前实现逐条模拟。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 每条指令只执行一条更新公式。
- 总和每轮翻倍，可作为理解与核对依据。
- 返回总和，不是单独某个变量。
易错点总结
[!yellow]
- 初始两个变量都设为零：所有更新后仍是零。
- 同一轮同时更新 x 和 y：把一条指令变成两次操作。
- 漏读第一条或最后一条指令：少执行一次翻倍。
- 只返回 x 或 y：并不是题目要求的总和。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 50. Pow(x, n) | 中等 | 每条指令都让x+y翻倍，最终是2的指令长度次方；一般幂可用快速幂，本题短输入可直接处理。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！