持1元和5毛者排队买票都能找零的方案数
哪些公司问过
传音1
答案要点
- 持 5 毛记 +1、持 1 元记 −1,合法条件是任意前缀和非负
- 问题等价于括号匹配,答案是卡特兰数
- 反射法:不合法序列与 1001 个 −1、999 个 +1 的序列一一对应
- 合法数 = C(2000,1000) − C(2000,999) = C(2000,1000)/1001
- 人可区分时结果再乘 1000!×1000!
易错点
- 把 1 元记成 +1,符号含义弄反导致约束写错
- 忘记区分人是否可区分,漏乘 1000!×1000!
- 直接给公式不说明反射法推导
面试官常见追问
- 卡特兰数还有哪些典型应用?
- 如果售票员一开始有 k 张 5 毛呢?
- 怎么用 DP 验证?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。