社招笔试记录:解码方案数、逆序计数与巧克力切分
- 轮次
- 笔试
- 时间
- 2026-11
- 来源
- 牛客网
《面试题目》
- 给定一个只含数字的字符串,按 A→1、B→2……Z→26 的规则解码,最多有多少种解码方式?
- 给定一个整数数组,求每个数字之后有多少个比它小的数字。
- 一块巧克力有 n 段,每段有一个口味值,把它切成 k 段连续的部分,每段的得分是这一段内不同口味的种类数,求所有段得分之和的最大值。
《参考解析》
解码方案数是线性 DP,0 的边界要单独想清楚。设 dp[i] 为前 i 个字符的解码方案数,dp[0] = 1。转移有两条:当前字符 s[i-1] 不为 '0' 时,它可以单独解码成一位数,dp[i] += dp[i-1];前两位 s[i-2..i-1] 落在 10 到 26 之间时,可以合并解码成两位数,dp[i] += dp[i-2]。0 的处理规则只有一句:'0' 不能单独解码,只能与前一位组成 10 或 20,所以首字符是 0、或出现 00、30、06 这类组合时该分支直接无效。帖主只过 83%,最可能漏的是「前一位是 0 时不能再与前一位拼成两位数」以及整串以 0 结尾的情况。实现上用两个变量滚动即可,空间 O(1),答案通常要求取模。要能顺手回答边界样例:"0" 返回 0、"10" 返回 1、"101" 返回 2、"100" 返回 1、"27" 返回 1。
统计右侧比它小的个数,标准解法是树状数组或归并排序,O(n log n)。从右往左扫,树状数组维护「已经出现过的值」的计数,先把值离散化(排序去重后取排名),扫到位置 i 时查询排名小于 rank(a[i]) 的前缀和,就是右侧比它小的个数,然后把 rank(a[i]) 加一。这一步的意义是:把「两两比较」的 O(n²) 变成「单点更新 + 前缀查询」的 O(log n)。重复元素要按「严格小于」处理,所以查询用 query(rank - 1) 而不是 query(rank),否则相等的元素会被算进去。归并排序的写法是在合并两个有序段时,右边元素出列就累加左边剩余个数,思路等价、常数更小,但树状数组更好写也更好讲。这题与 LeetCode 315 是同一道。
巧克力切分是「划分型 DP + 线段树优化」,朴素写法必然超时。定义 dp[j][i] 为前 i 段切成 j 份的最大得分,转移是 dp[j][i] = max(dp[j-1][t] + distinct(t+1..i)),其中 t 从 j-1 到 i-1,复杂度 O(k n²),n 到了几万就过不去。优化的关键在于固定层数 j、从左到右扫 i 时,把每个 t 的候选值 dp[j-1][t] + distinct(t+1..i) 放进一棵支持「区间加、区间最大值」的线段树:当 i 向右移动、加入新口味 c 时,只有那些起点 t 落在「c 上一次出现的位置」到 i-1 之间的区间,其 distinct(t+1..i) 会因为新增 c 而加一,其余区间不变;于是做一次区间加一,再查询 [j-1, i-1] 的最大值即为 dp[j][i]。每层扫一遍,每步一次区间加与一次区间查询,总复杂度 O(k n log n)。实现时用 last[c] 记录每种口味上一次出现的位置,初始把 t 位置的初值设为 dp[j-1][t](此时区间为空、distinct 为 0),不可达的位置设负无穷。
这场笔试反映的是社招算法题的一个典型趋势:单题不难在思路,难在数据规模逼着你把 O(n²) 换成 O(n log n)。赛前准备的重点不是多背题,而是把「区间加 + 区间最大值」「单点更新 + 前缀和」「滑动窗口 + 单调队列」这三种优化套路与对应的题型绑定起来,看到「对每个位置统计某种计数」先想树状数组,看到「划分成 k 段求最优」先想能否把转移中的一项写成区间操作。
做题节奏:三道题里第一道是送分题但边界多,先做、写完立刻用边界样例自测;第二道是模板题,确认「严格小于」与离散化;第三道如果没有线段树把握,先写 O(k n²) 的暴力拿部分分,再考虑优化——笔试按测试点给分,空着是最差的选择。