题目描述

点这里

思路分析

约瑟夫问题。
数组链表模拟/递推递归，都能做。
暴力模拟的方法就不讲了，当成链表节点就好。主要写下递归递推做法。递推/递归的关键是找到递推关系。
设 f ( n , m ) f(n,m) f(n,m)为问题规模为 n , m n,m n,m时问题的答案。
则画图重新标号+映射分析可得递推式 f ( n , m ) = ( f ( n − 1 , m ) + m )   m o d   n f(n,m)=(f(n-1,m)+m)\ mod\ n f(n,m)=(f(n−1,m)+m) mod n

代码实现

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        if(!n) return -1;
        if(n==1) return 0;
        return (LastRemaining_Solution(n-1,m)+m)%n;
    }
};