去哪儿 AI 应用开发（Java）10.11 笔试：翻转灯颜色求有效对数量

《面试题目》

1. 单选题（10 道）：操作系统、SQL、后端、Agent 相关内容。
2. AI Coding（1 道）：用平台自带的 AI 助手限时 20 分钟完成，要求跑到用例全部通过。
3. 算法题：有一排灯，每盏灯有两种颜色（R/B），每盏灯还有一个权重，给定目标值 t。「有效对」定义为相邻两盏灯同时满足三个条件——颜色不同、权重之和等于 t、两盏灯的索引一奇一偶；每次操作给出一个位置、翻转该位置的颜色，要求每次翻转之后输出当前有效对的数量。

---

《参考解析》

笔试构成：单选的覆盖面和 AI Coding 的用法

选择题只有 10 道但铺得很散——操作系统（进程线程、内存管理、IO）、SQL（连接、索引、聚合）、后端基础、Agent 概念，这类组合考的是广度而不是深度，靠平时积累，临场不值得花太多时间。AI Coding 由平台自带助手完成，20 分钟一次通过 32 个用例，说明这类题的评分只看用例通过情况：写完之后一定要自己通读输入输出格式、补齐边界用例（空输入、单元素、极值、重复调用），别把「AI 给的代码看着对」当成通过。考试最后一批的复盘也说明这套题整体难度不高，真正的失分点往往是细节和边界。

算法题：把 O(n) 的重复扫描压成 O(1) 的增量更新

这道题的关键观察只有一个：「有效对」被限定为相邻的两盏灯，所以翻转位置 p 的颜色时，只有 (p-1, p) 和 (p, p+1) 这两对的状态会变，其余位置的对都不受影响。于是不需要每次翻转后重扫整排灯。

维护一个布尔数组 can[i] 表示第 i 与第 i+1 盏灯是否构成有效对，条件是 col[i] != col[i+1] && w[i] + w[i+1] == t（权重不参与翻转，所以 w 的和可以预存，甚至可以把整条 can 预计算好）。再维护一个全局计数 ans = Σ can[i]，初始扫一遍 O(n)。每次翻转位置 p：

1. 先对 k = p-1 和 k = p 两个受影响的下标，把旧的 can[k] 从 ans 里减掉；
2. 翻转 col[p]（R 变 B、B 变 R）；
3. 对同样两个下标重新判定 can[k] 并加回 ans；
4. 输出 ans。

翻转与查询都是 O(1)，总复杂度 O(n + q)。暴力地在每次翻转后扫一遍是 O(nq)，只能过一部分用例——这也是那场笔试里暴力解只拿到 30% 通过率的原因。

容易错的几处：边界——p 在两端时只有一对受影响，两个下标的循环必须写成「k 在 p-1 与 p 中取值，且 0 ≤ k < n-1」；顺序——必须先减旧值再翻转再加新值，否则同一对会被减错一次；条件三——在「相邻」的前提下，i 与 i+1 天然奇偶不同，这条条件自动成立，所以判定里可以不写；但如果题面允许的有效对是任意两个位置（索引一奇一偶但不要求相邻），那 can 的定义就要改，增量更新也不再成立，必须先确认清楚再动手。

参考实现（伪代码，可以照这个结构落到具体语言里）：

can(i): i + 1 < n and col[i] != col[i + 1] and w[i] + w[i + 1] == t

ans = number of i in [0, n-2] with can(i)
for each query p:
    for k in (p - 1, p):
        if 0 <= k < n - 1: ans -= can(k)
    col[p] = flip(col[p])
    for k in (p - 1, p):
        if 0 <= k < n - 1: ans += can(k)
    print(ans)

如果题面里的翻转次数和灯的数量都很大，输入输出也要注意用缓冲区一次性读写，别在循环里逐次刷新输出。