约瑟夫环:从 2 开始隔一个删,求最后两人
哪些公司问过
答案要点
- 题意建模:每隔一人删除即步长 2 的约瑟夫环,最后两人是幸存者和最后被删者
- 模拟法:循环链表或队列,队首出队再入队一次后删除下一个,O(n)
- 递推(0 下标):f(1)=0,f(m)=(f(m-1)+2)%m 得幸存者;g(2)=1 起同式递推得最后被删者
- 闭式:n=2^m+L(0≤L<2^m)时幸存者为2L+1;n≥3且n=3·2^m+L(0≤L<3·2^m)时最后被删者为2L+1
- 边界:n=1 只剩一人,n=2 直接返回 1 和 2;用小 n 手动模拟验算
易错点
- 把题意理解成从 1 开始删或步长 3,删除顺序错位
- 递推中 0 下标与 1 下标混用,结果偏 1
- 忽略 n=1、n=2 的边界,或数组模拟时频繁删除导致 O(n²)
面试官常见追问
- 递推 f(m)=(f(m-1)+2)%m 是怎么来的?
- 如果步长改成任意 k 怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。