2020-03-30(62 圆圈中最后剩下的数字）

这道题比较简单，看题目能够想到的是循环链表，不过java中没有对应的组件，如果要用循环列表的话需要自己实现一个。懒得花这个时间，就用list模拟了。因为涉及到要移除元素，我使用了ArrayList，后来看到评论说用其他组件有超时的问题。不过即使用了这个ArrayList，耗时也不是很理想，还有一种数学推导方法，不是很好理解，但是比较简洁轻便。

方法一：用ArrayList模拟

    ArrayList<Integer> mList =  new ArrayList<Integer>();
    public int lastRemaining(int n, int m) {
        initialList(n);
        if(n < 1 || m < 1){
            return -1;
        }
        return getLastNum(m);
    }

    public int getLastNum(int m){
        int cur = m - 1;
        while(mList.size() > 1){
            int size = mList.size();
            if(cur > size - 1){
                cur = cur % size;
            }
            mList.remove(cur);
            cur += m - 1;
        }
        if(mList.size() > 0){
            return mList.get(0);
        }else{
            return -1;
        }
    }

    public void initialList(int n){
        for(int i = 0; i < n; i++){
            mList.add(Integer.valueOf(i));
        }
    }

方法二：数学推导，约瑟夫环
假设 n = 5, m = 3，列出元素的删除过程
index=0 : 0 1 2 3 4
index=1 : 3 4 0 1 | 3 4 0 1
index=2 : 1 3 4 | 1 3 4
index=3 : 1 3 | 1 3
index=4 : 3
从下往上进行倒推：
k=1 -----> f(1) = 0;
k=2 -----> f(2) = (0 + 3) % 2 = 1;
k=3 -----> f(3) = (1 + 3) % 3 = 1;
k=4 -----> f(4) = (1 + 3) % 4 = 0;
……
……
k = n ------> f(n) = (f(n-1) + m) % n
具体实现如下

public int lastRemaining(int n, int m) {
        if(n < 1 || m < 1){
            return -1;
        }
        int result = 0;
        for(int k = 2; k < n + 1; k++){
            result = (result + m) % k;
        }
        return result;
    }