题目描述
 0, 1, …, n-1这n个数字排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。


方法很多,这里记录几种用的比较多的解法

解法1:

  第一想法肯定是使用环形链表

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        class ListNode {
            int val;
            ListNode next = null;        
            ListNode(int val) {
                this.val = val;
            }
        }

        if (n <= 0 || m <= 0) {
            return -1;
        }       
        ListNode head = new ListNode(0);
        ListNode node = head;
        for (int i = 1; i < n; i++) {//先穿成串
            node.next = new ListNode(i);
            node = node.next;
        }
        node.next = head;//将链表尾部和头部连起来形成环

        for(int i = 0; i<n-1; i++) {//n个节点要删n-1次
            for(int j = 0; j<m-1; j++){//每删一次都要从当前节点移动m-1次
               node = node.next;//初始的节点是尾节点,next属性是指向头结点的。
            }
            node.next = node.next.next;//移动就绪后,就删除
        } 
        return node.val;
    }
}

解法2:

  其实也可以不用环形链表,巧妙的将使用的链表或者数组设计成循环的就行。考虑一些边界,或者是利用取模来达到循环的目的。如(removeIndex+m-1)%list.size(),如果超过size,就取模,就和钟表走14个钟头,其实就是两点是一个道理。而size也会同步更新,这个解法比较巧。同样这个LinkedList可以改成数组没有问题。

import java.util.LinkedList;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n<1 || m<1)
            return -1; 
        LinkedList<Integer> list = new LinkedList<Integer>();
        for(int i=0;i<n;i++)
            list.add(i);
        int removeIndex=0;
        while(list.size()>1){
            removeIndex=(removeIndex+m-1)%list.size();
            list.remove(removeIndex);
        }
        return list.getFirst();
    }
}

解法3:

  找到规律,利用数学推导公式,从而求解。(我估摸着有点烧脑,为了省点头发,我决定以后再来研究)其实可以看到,这个推导的公式和解法2的取模比较相似,只不过一个是顺向思维求解,一个是逆向思维求解(我没动脑子,这个是凭感觉说的。)

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n<1 || m<1)
            return -1; //出错
        int last = 0;
        for(int i = 2; i<=n; i++){
            last = (last+m)% i;  //这里是i不是n!!!
        }
        return last;
    }
}