拼多多9月22日笔试面经（四道编程题）

《面试题目》

1. 给一串数字如 222331144，相同的且连在一起的可以一次清空，问最少几次清空？（通过率 100%）
2. 只含 a 和 b 的字符串，问能组成的最长的「连续 a + 连续 b + 连续 a」序列有多长？可以删除元素，允许某一段长度为 0。（通过率 100%）
3. 给 n 个苹果的 x、y 坐标，问要圈出 c 个苹果的最小正方形边长是多少？（作者用堆，通过率 40%）
4. 给一个括号序列，两种操作：Q l r 查询 l 到 r 区间的括号是否合法；F l r 把 l 到 r 区间的括号反转（左右括号互换）。作者只写了暴力。（通过率 56%）

《参考解析》

第 1 题：最少清空次数。一次只能清空一段连续且相同的数字，那么把原串做「相邻去重」压缩成若干段（222331144 → 222|33|11|44，共 4 段），因为相邻段的数字必然不同，清掉任意一段都不会让左右两段合并，所以顺序不影响结果，答案就是段数。写法是一次线性扫描：cnt = 0; for i in range(n): if i == 0 or s[i] != s[i-1]: cnt += 1，时间 O(n)、空间 O(1)。这题的失分点几乎全在读题——作者提到自己一开始理解成了”区间内相同数量的货品”，拐到前缀和上去了，说明拿到题先花 30 秒确认操作定义（清空的是什么、一次能清多少、能不能不连续）比急着写代码重要得多。

第 2 题：a+b+a 三段最长子序列。这是典型的分段 DP：设 dp1 为当前只取第一段（全 a）时的最大长度，dp2 为取到 a+b 两段时的最大长度，dp3 为取到 a+b+a 三段时的最大长度，扫一遍字符串按字符更新：

dp1 = dp2 = dp3 = 0
for ch in s:
    if ch == 'a':
        # 注意先算 dp3 再用旧 dp2，避免同一字符被两段共用
        dp3 = max(dp3, dp2) + 1
        dp1 = dp1 + 1
    else:  # ch == 'b'
        dp2 = max(dp2, dp1) + 1
print(dp3)

转移的物理含义：遇到 a 时，它可以接在第一段 a 后面（dp1+1），也可以开启第三段 a（接在 dp2 后面）；遇到 b 时，只能接在 dp1 后面形成第二段 b（或用 dp2+1 延长第二段）。两个易错点：①更新顺序——dp3 必须用上一轮的 dp2 来更新，所以要么先算 dp3 再算 dp1，要么用临时变量保存旧值，否则同一个 a 会被第一段和第三段共用、答案偏大；②题目允许某段长度为 0，所以初值全为 0 即可，不需要特判。答案取 dp3。

第 3 题：圈出 c 个点的最小正方形边长。作者用堆只过了 40%，说明方向不对。正解是二分答案 + 双指针/滑动窗口：正方形的边长 L 一旦确定，最优的正方形一定可以让左边界贴住某个点的 x、下边界贴住某个点的 y（否则可以平移缩小），所以只需枚举候选的 x 区间。做法：①二分 L（下界 0，上界 max(max_x - min_x, max_y - min_y)）；②判定时把点按 x 排序，用双指针维护一个宽度为 L 的窗口，窗口内再按 y 排序，检查是否存在高度为 L 的区间能容纳 ≥ c 个点——可以用有序容器（C++ multiset、Java TreeMap）滑动维护，判定复杂度 O(n log n)；③整个算法 O(n log² n)，n 到 1e5 也能过。单调性是二分的前提：L 越大能圈住的点只会更多，所以判定函数单调，可以二分。用堆做”取最近的 c 个点”错在把二维的 L∞ 距离问题和一维排序混为一谈。

第 4 题：括号序列的区间查询与区间反转。这题的判定要用前缀和：把 ( 记 +1、) 记 -1，则区间 [l, r] 是合法括号序列 ⟺ ①区间和为 0；②区间内所有前缀和 ≥ 0（等价于最小前缀和 ≥ 0）。查询 Q 就是求区间和与区间最小前缀和。难点在操作 F（区间反转）：反转不仅是左右括号互换，顺序也颠倒了，等价于把区间内的数组反向后取负。线段树每个节点维护四个量就能支持：sum、min_prefix（最小前缀和）、max_prefix（最大前缀和）、max_suffix（最大后缀和）。反转懒标记的转移是：

sum'        = -sum
min_prefix' = -max_suffix   （原来是后缀，反转后变成前缀）
max_prefix' = -min_suffix

同时交换左右儿子的顺序。有了这个标记，Q 和 F 都是 O(log n)，总复杂度 O((n + q) log n)，能过 2e5 级别的数据；纯暴力是 O(nq)，只能拿部分分。这题和第三题都说明同一件事：看到 n, q ≤ 2×10^5 这种规模，先估复杂度（O(nq) 必超），再去想线段树/树状数组/二分这类 log 级别的结构，别用暴力硬混。

整体复盘：这场笔试的难度是”前两题送分、后两题拉开区分度”。前两题只要读清题意 + 一遍线性扫描/DP 就能满分；后两题是标准的 ACM 中档题（几何 + 数据结构），没有系统刷过专题很难现场推出来。备考建议：把「读题确认操作定义」「先估复杂度再选结构」这两条变成条件反射，比多背几个模板更值钱。作者提到提前 20 分钟交卷去吃饭，其实后两题即便没思路，也要把暴力写稳拿部分分——这场的 40% 和 56% 就是暴力分。