中国电信机考笔试:编号记录变更与字符串三等分切点
- 轮次
- 笔试
- 时间
- 2026-11
- 来源
- 牛客网
《面试题目》
- 编号记录变更:每个编号初始没有记录(可视为 0)。按顺序处理
PUT key value(设为 value,无记录则先建立)、INCREASE key delta(增加 delta,未登记则按 0 起步)、REMOVE key(有记录才可删除,否则本次失败)。每条成功的指令计为一次成功变更,并按编号累计成功变更次数;删除记录不清除累计次数。全部指令处理完后,输出三个数:成功变更总数、失败的 REMOVE 指令数、以及最终仍保留且数值不为 0、累计成功变更次数恰为 1 的编号个数。 - 字符串合法切点:给定只含 A、B、C 的字符串,找两个切点 u、v(1 ≤ u < v < m),把串切成三个非空连续部分;要求三部分中 A 的数量相同、B 的数量也相同(C 不要求)。输出字典序最小的 (u, v),无解输出
-1 -1。
《参考解析》
第一题是纯粹的哈希表模拟,关键在两张表分开维护。 一张表存「当前仍存在的编号及其数值」,另一张表存「每个编号的历史成功变更次数」。三条指令的规则要逐条对齐题意:PUT 与 INCREASE 无论编号是否存在都会成功并让计数加一,INCREASE 对未登记的编号按当前值 0 处理(用 map[key] += delta 的默认值语义即可);REMOVE 只在当前表里存在该编号时才成功,删除时只删「当前值」那张表,历史计数必须保留,否则同一编号被删除后重新创建会把次数清零,最终统计就会算错。失败的指令不改变任何计数。最后遍历当前表,value != 0 && count == 1 才计入答案。复杂度 O(M),数值用 64 位整型承载。
以样例验证:编号 8 经历 PUT、REMOVE、PUT 三次成功,最终值为 0(不计入);编号 9 创建后被移除,第二次 REMOVE 失败(失败计数 1);编号 11 只成功设置一次且值为 −2(计入);编号 12 从未存在,REMOVE 失败(失败计数 2)。输出 6 2 1,与题面一致。
第二题的核心是先算总量再定前缀。 设全串 A 的数量为 ca、B 的数量为 cb,三段等分要求 ca 与 cb 都能被 3 整除,否则直接无解。设每段应有 a = ca/3 个 A、b = cb/3 个 B,则第一个切点 u 必须满足前缀 [1..u] 中 A 恰为 a、B 恰为 b;第二个切点 v 必须满足前缀 [1..v] 中 A 恰为 2a、B 恰为 2b。由于要求字典序最小,从左到右扫描,第一个满足第一组条件的位置就是 u(且必须留出后两段非空,即 u ≤ m−2);从 u+1 开始继续扫描,第一个满足第二组条件且 v ≤ m−1 的位置就是 v。C 不参与判定,只影响位置。
为什么这样扫描得到的就是字典序最小解。 字典序先比 u 再比 v,因此 u 取到满足条件的最小值即可;在 u 固定后,v 同样取满足条件的最小值。前缀计数一旦达到目标值,之后只会继续增大,所以「第一个满足条件的位置」就是唯一候选,不存在回头再选更优的情况。整体复杂度 O(m),空间 O(1)。
两类题的共同失分点。 第一题容易错在「删除后重建立是否继承计数」和「失败指令是否计数」这两处语义;第二题容易错在边界——切点必须保证三段都非空(u 至少留 2 个字符,v 之后再留 1 个),以及把「三段 A、B 数量相同」误读成「三段完全由相同字符组成」。笔试里先手写两三组小样例(全 A、含 C、总数不能被 3 整除)跑一遍,能挡住大部分边界错误。