约瑟夫问题

问题：约瑟夫问题是一个非常著名的趣题，即由n个人坐成一圈，按顺时针由1开始给他们编号。然后由第一个人开始报数，数到m的人出局。现在需要求的是最后一个出局的人的编号。
给定两个int n和m，代表游戏的人数。请返回最后一个出局的人的编号。保证n和m小于等于1000。
一：递推公式法：
链接：https://www.nowcoder.com/questionTerminal/11b018d042444d4d9ca4914c7b84a968
import java.util.*;
 
public class Joseph {
    /*
     * 编号为(0~n-1)
     */
    public int getResult(int n, int m) {
        if (n < 0 || m < 0) {
            return -1;
        }
        int last = 0;
        for(int i=2;i<=n;++i){
            last = (last+m)%i;
        }
        // 因为实际编号为(1~n)
        return (last+1);
    }
}
 
二：使用链表，
 
import java.util.*;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        
        /*
        *约瑟夫问题：用链表真是模拟提出过程。
        将n个数填到链表中(此题是0-n-1)，当每循环m时，删除它,直到只剩下一个元素时,此元素就是最后的返回值
        */
        if(n<=0||m<=0)
            return -1;
        LinkedList<Integer> list=new LinkedList<Integer>();
        for(int i=0;i<n;i++)
            list.add(i);
        int dt=0;
        while(list.size()>1){
            //找到删除的位置，且后一次位置是(前一个删除位置+m-1)%list.size(),
            //这里减一是因为每次删除一个以后，后面的元素会向前移动一位，所以只要从删除位置向后找m-1个就行了
            int delPos=(dt+m-1)%list.size();
            
            list.remove(delPos);
            //这里是为了防止delPos是最后一个元素，所以归一化
            dt=delPos%list.size();
        }
        return list.get(0);
    }
}
 