百度笔试 9 月 3 日机考面经

《面试题目》

1. 如何判断一个二进制字符串能否通过反复删除相邻的 01 或 10 变成空串？
2. 如何统计矩阵中被城墙完全围住的村庄数量？
3. 如何求指定进制中不含前导零的第 K 个长度为 L 的回文串？
4. 如何在图上升级至多 K 条边后，求 0 到 n-1 的最大瓶颈带宽？

《参考解析》

1. 删除一对不同字符不会改变 0 和 1 的数量奇偶关系；用栈模拟相邻消除即可，最终栈为空的字符串可核销。也可以利用二进制串长度为偶数且 0、1 数量相等这一不变量快速判定。
2. 从矩阵边界的村庄做多源 BFS，标记所有能连到外界的村庄；总村庄数减去已标记数量就是被围住的数量。
3. 回文串由前半段唯一决定。先计算最小合法前缀的排名，再将排名转换为 B 进制前缀并镜像，注意长度奇偶决定中间位是否重复。
4. 对答案带宽二分，检查是否存在一条路径，使小于候选带宽的边通过至多 K 次升级后全部满足阈值；检查过程可用 0-1 BFS 或带升级次数的最短路完成。