阿里工程笔试题解（GCD、括号贪心、LCA）

面试题目

笔试环境

语言：Java

---

第一题

数学推导题，核心公式：

t = gcd(d, m)
a %= t
ans = m - t + a

---

第二题

括号序列贪心修复题：

• 维护变量 now = 0，将 ( 看成 +1，) 看成 -1，从左往右累加。
• 若 now 将要变为 -1，则把该 ) 改成 (，记录到 ans。
• 再反向遍历，now = 0，将 ( 看成 -1，) 看成 +1，从右往左累加。
• 若 now 将要变为 -1，则将该 ( 改成 )，记录到 ans。

---

第三题

树上三元组 LCA 查询，输入 (r, u, v)：

x = lca(u, r)
y = lca(v, r)

if x == y:       输出 lca(u, v)
if lca(x, y)==x: 输出 y
if lca(x, y)==y: 输出 x
// 无其他情况

---

参考解析

第一题：GCD 数论

• 问题本质是在模 m 意义下对 d 的倍数取余的最优化问题。
• t = gcd(d, m) 表示 d 在模 m 下能到达的最小正步长。
• a %= t 将目标值归约到 [0, t) 区间内。
• ans = m - t + a 表示从 0 出发绕一圈能达到的最接近目标的值，需熟悉扩展 GCD 思路。

第二题：括号贪心双向扫描

• 经典「最少修改使括号合法」贪心模板，时间复杂度 O(n)。
• 第一遍从左到右消除多余的 )；第二遍从右到左消除多余的 (。
• 两遍扫描后 ans 即为需要翻转的括号集合，注意两次扫描互不干扰。
• 需熟练掌握括号序列的计数不变量：now 不能为负。

第三题：树上 LCA 三元组

• 以 r 为根重新定义树的根，查询 u、v 在以 r 为根时的 LCA。
• 核心思路：x = lca(u,r)，y = lca(v,r) 捕获 u、v 各自与根的「汇合点」。
• 三种情况覆盖所有拓扑关系，结论简洁，证明可用 DFS 序 + 深度分析。
• 实现上需预处理倍增 LCA，查询 O(log n)，整体复杂度 O(n log n)。