恒生电子 Java 笔试：SQL、滑窗与折扣券 DP

《面试题目》

1. 单选题与不定项：考点很杂，覆盖 Java 基础、数据结构、计算机网络和操作系统。
2. 填空题：题目基本把提示给全了。
3. 编程题一：SQL 编程，题干很长、逻辑还复杂。
4. 编程题二：给定一个字符串，求出其中符合”连续三个字母为 red”（顺序不计）的子串个数。
5. 编程题三：给定一个数组和一张半价向下取整的折扣券，数组每个值只能选 0 次或 1 次、券只能用一次，问能不能凑出给定的值 m。

《参考解析》

滑窗统计”连续三个字符是 red 的排列”：因为长度固定为 3，所以窗口大小是常数，只需要维护窗口内 r、e、d 三个字符的计数：右指针进一个字符并计数，计数满足”三个都恰好为 1”就累计一个答案，然后左指针出窗口并减计数，整体 O(n)、O(1) 空间。判断题干时有两个口径要先确认：一是”顺序不计”指三个字符可以任意排列（即窗口内恰好是 r、e、d 各一个），判断条件应该是三个计数都等于 1，而不是都大于等于 1——后者在窗口里出现第四个字符时会误判；二是大小写和其他字符怎么处理。只过 90% 通常就栽在边界上：字符串长度小于 3 要直接返回 0，窗口还没填满 3 个字符时不能开始判断，滑动的加减顺序写反会导致计数错位。这类题交卷前值得写个暴力三重循环做小数据对拍，几十行就能验出边界问题。

带折扣券的凑数问题怎么建模：先看清状态维度。每个元素最多选一次、券最多用一次、用券的元素按 floor(x/2) 计入，那么”选一个子集”和”其中一个元素是否用了券”是两个独立维度：最直白的建模是 dp[i][s][used]，表示前 i 个数能否凑出和 s、券是否已用，转移分三种——不选第 i 个、选且不用券、选且用券（要求 used 还是 false）。n 和 m 都不大时直接二维数组加布尔值就够；m 到几万、n 到几百时用 bitset 加速：把”可达的和”压成二进制位串，选一个数就等价于整体左移若干位再和自己求或，用券那一层单独开一组 bitset 做同样的平移，常数能降一两个数量级。还有两种笔试常见做法：如果 n 很小（二十以内）可以枚举用了券的那个元素，对每个候选跑一次 0/1 子集和；如果 m 不大且要求的是”最少用多少个数凑出”，就把状态定义成最小个数而不是布尔值。细节上”向下取整”意味着要全程用整数运算，奇数元素省的额度是固定的，别用浮点算折扣再取整，容易在边界上差一。

笔试时间怎么分配：这套卷子的结构是”选择不定项杂 + 填空送分 + 三道编程”，合理的顺序是先把填空和选择快速做完，再按”有把握 → 有可能 → 没思路”做编程题。原帖里第一题 SQL 题干长、逻辑复杂，第二题滑窗差分 10%，第三题思路乱掉最后没做出来，这就是典型的在同一道题上耗掉其他题时间的形态。止损线要在开考时就定好，比如单题超过二十分钟没进展就先去拿别的分，回头再看；同时要有意识地准备套路——SQL 的窗口函数与多表连接、固定长度滑动窗口、bitset 加速的子集和、输入输出加速——这几类在笔试里反复出现，练过和没练过的差距比”临场想出来”大得多。