面试题库 › Java 后端 › 持1元和5毛者排队买票都能找零的方案数

持1元和5毛者排队买票都能找零的方案数

难度 ★★★在 1 场真实面经中被问到 方向:Java 后端考点:数学与智力题

哪些公司问过

传音1

常见岗位:Java 后端

答案要点

  1. 持 5 毛记 +1、持 1 元记 −1,合法条件是任意前缀和非负
  2. 问题等价于括号匹配,答案是卡特兰数
  3. 反射法:不合法序列与 1001 个 −1、999 个 +1 的序列一一对应
  4. 合法数 = C(2000,1000) − C(2000,999) = C(2000,1000)/1001
  5. 人可区分时结果再乘 1000!×1000!

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题