面试题库 › 客户端 › 约瑟夫环:从 2 开始隔一个删,求最后两人

约瑟夫环:从 2 开始隔一个删,求最后两人

难度 ★★★在 1 场真实面经中被问到 方向:客户端

哪些公司问过

小红书1

常见岗位:安卓

答案要点

  1. 题意建模:每隔一人删除即步长 2 的约瑟夫环,最后两人是幸存者和最后被删者
  2. 模拟法:循环链表或队列,队首出队再入队一次后删除下一个,O(n)
  3. 递推(0 下标):f(1)=0,f(m)=(f(m-1)+2)%m 得幸存者;g(2)=1 起同式递推得最后被删者
  4. 闭式:n=2^m+L(0≤L<2^m)时幸存者为2L+1;n≥3且n=3·2^m+L(0≤L<3·2^m)时最后被删者为2L+1
  5. 边界:n=1 只剩一人,n=2 直接返回 1 和 2;用小 n 手动模拟验算

易错点

面试官常见追问

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