携程9月6日机考笔试面经

《面试题目》

1. 如何用栈匹配合法括号串，并统计内部长度能被 m 整除的匹配区间数量？
2. 如何计算周期灯阵中所有区间的相位贡献？
3. 如何在有限状态下统计字符串或数组区间的周期性质？

《参考解析》

1. 左括号下标入栈，右括号弹出最近的左括号。对每一对计算 R-L-1，用模运算判断是否计数；相邻括号的内部长度为 0，也应计入。
2. 将位置按周期取模分组，先建立后缀计数，再把每个起点与满足相位条件的终点配对。对周期长度按因子或商分块，可把朴素的双重枚举降到调和级数复杂度。
3. 先明确状态是否只由前缀摘要决定，再用前缀和、哈希或动态规划保存摘要；遇到重复周期时复用已计算的状态，避免逐区间重新扫描。