360 笔试 10.10 记录：40 道选择与两道算法题

《面试题目》

1. 选择题 40 道，单选多选混合，涵盖 Linux、大模型、安全、HTML5、Java、Python、网络、操作系统。
2. 算法题 1：给定一个 n 个数的 b 数组，在 a 中为每个 b 里的数找大于等于它的数，使选出的数总和最小（原帖思路：排序加二分）。
3. 算法题 2：消除一个数字序列中的回文串，最后删空，求最小步数（原帖思路：dp[l, r]）。

《参考解析》

排序加二分这类匹配题为什么是对的。题目的结构是「给定两个序列，为 b 中每个元素在 a 中找一个不小于它的数配对，使选出的数之和最小」，本质是一个带下界约束的指派问题。原帖给出的排序加二分正是这个结构下的贪心解法：先把 a 与 b 都排序，对 b 中每个元素在 a 里二分查找第一个大于等于它的位置（lower_bound），找到就配上并把它从候选里移除，找不到就说明这个 b 无法满足。为什么尽量配「刚好够大」的那个是对的：如果 b[i] 配了一个更大的 a[x] 而 a[y]（y < x 且 a[y] ≥ b[i]）还在，把这个 a[x] 换成 a[y] 只会让总和更小或不变，且不影响后续更大的 b 的可选集合（因为 a[y] 比 a[x] 更小、更「不值钱」），所以按「每个 b 都选满足条件下最小的可用 a」逐项决策不会让全局变差。

实现上比「一边做二分一边从数组里删元素」更省事的是排序后用双指针：i 指向 a、j 指向 b，如果 a[i] ≥ b[j] 就配对并把两个指针都推进，否则只推进 i（这个 a 太小，留着给不了后面的 b 用，因为 b 已排序、后面的更大）。是否要求 a 中每个元素只能用一次、以及 b 里有没有重复值，会决定双指针还是 multiset 写法，读题时务必确认。

区间 DP 消除回文串。设 dp[l][r] 表示把区间 [l, r] 删空所需的最小步数。三种转移覆盖全部情况：一是枚举分割点 k，把区间拆成两段分别删，dp[l][r] = min(dp[l][k] + dp[k+1][r])；二是如果 s[l] == s[r]，可以把两端放在同一次消除里完成，先去删中间再一起抹掉两端，dp[l][r] = min(dp[l][r], dp[l+1][r-1])；三是更一般的合并，若 s[l] 与位置 m（m ≤ r 且 s[m] == s[l]）相同，可以先把 [l+1, m-1] 删空，再让 s[l] 与 s[m] 归入同一次消除，dp[l][r] = min(dp[l][r], dp[l+1][m-1] + dp[m][r])。边界是 dp[i][i] = 1、空区间 0，按区间长度从小到大递推（不要写成记忆化递归，n 稍大就可能爆栈或重复计算）。复杂度 O(n^3)，n 在 300～500 以内可接受；数据更大时要靠「只有相同字符的位置才需要枚举」来剪枝，或确认是否只要求消除连续回文（那可以用更小的状态）。这题和帖主前一天遇到的「嵌套数组消除回文」是同一个骨架，区别在于嵌套结构要先摊平成序列或建树，而且题面如果限制只能在同一层内消除，就不能简单摊平。

40 道混合选择题透露出什么。涵盖 Linux、大模型、安全、HTML5、Java、Python、网络、操作系统，说明这套卷子想筛的是「基础面足够宽」的候选人，而不是某个方向的专家。复习时可以把每一科压到几个必考结论：Linux 的文件权限与常用命令语义、系统调用的直观理解；大模型的 Transformer 结构、微调与提示、RAG 与工具调用各自解决什么；安全里的 XSS 与 CSRF 成因和防御、对称与非对称加密的典型算法；HTML5 的语义化标签与本地存储 API；Java 的集合与异常体系；Python 的可变默认参数陷阱、GIL 的含义；网络的分层、TCP 三次握手与四次挥手、HTTP 状态码语义；操作系统的进程与线程、死锁四条件、内存分页。这些结论用一小时速查就能过完，比继续啃算法更有性价比。

笔试的得分策略。40 道选择加两道算法，如果选择部分平均每题不到一分钟、算法题各留二十分钟，时间分配才合理。多选题最忌讳「感觉都对」而反复纠结，遇到完全没把握的先按第一直觉选掉并标记，最后再回头看——多选题的期望收益远低于把算法题的正确版本写出来。算法题上场后先写暴力或 DP 的正确版本提交，确认能过样例和部分用例，再去优化常数或处理边界；「思路对但没时间写完」是这场笔试最常见的失分形态，而每道题的最低可运行版本通常只要十五分钟。