孩子们的游戏(圆圈中最后剩下的数)

import java.util.ArrayList;

public class Solution {
    public  int LastRemaining_Solution(int n, int m) {    
    	if(n==0)
    		return -1;
    	ArrayList<Integer> array=new ArrayList<>();
    	for(int i=0;i<n;i++){
    		array.add(i);
    	}
    	int tempIndex=(m-1)%array.size();//用于记录最初需清除的数字索引
    	while(array.size()!=1){ 
    		//System.out.println(array.get(tempIndex));
    		array.remove(tempIndex);
    		tempIndex=(tempIndex+(m-1))%array.size();//记录当前索引
    	}
    	return array.get(0);
    }
}

public class Solution {
    class Child{
        int index;
        Child next;
        public Child(int index){
            this.index = index;
        }
    }
    public int LastRemaining_Solution(int n, int m) {
        if(m==0)
            return -1;
        if(n==0)
            return 0;
        Child laosiji = new Child(0);
        Child kaichele = laosiji;
        for(int i = 1;i<n;i++){
            Child daidaiwo = new Child(i);
            kaichele.next = daidaiwo;
            kaichele = daidaiwo;
        }
        kaichele.next = laosiji;
        Child qingshuaka = laosiji;
        while(qingshuaka.next!=qingshuaka){
            Child dixueshengka = null;
            for(int i = 0;i<m-1;i++){
                dixueshengka = qingshuaka;
                qingshuaka = dixueshengka.next;
            } 
            qingshuaka = qingshuaka.next;
            dixueshengka.next = qingshuaka;
        }
        return qingshuaka.index;
    }
}

/*
//法一：C++实现 list容器+其迭代器实现圆形链表 （约瑟夫环问题）
class Solution {
public:
    int LastRemaining_Solution(int n, int m)//n为人数
    {
        if(n<1||m<1)
            return -1;
        list<int> numbers;
        for(int i=0;i<n;i++)
            numbers.push_back(i);
        list<int>::iterator current=numbers.begin();
        while(numbers.size()>1)
        {
            for(int i=1;i<m;i++)//走m-1步到达第m个数处
            {
                ++current;
                if(current==numbers.end())
                    current=numbers.begin();
            }
            
        	list<int>::iterator next=++current;
            if(next==numbers.end())
                next=numbers.begin();
            --current;
            numbers.erase(current);
            current=next;
        }
        return *current;//对迭代器取值，等价于对指针取值
    }
};
*/
//法二：找出规律,通项为：f(n,m)={f(n-1,m)+m}%n。
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;
        }
        return last;
    }
};

   /*约瑟夫问题，求递推公式，每轮的序列中最后出序列的数都是同一个*/
     public int LastRemaining_Solution(int n,int m) {
        if(n < 1 || m < 1)
        	return -1;
    	if(n == 1){
        	return 0;
        }
        return (LastRemaining_Solution(n-1, m)+m)%n;
    }

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;
        }
        return last;
    }
}

循环队列：
class node
{
	int num;
	node next;
	node (int num)
	{
		this.num = num;
	}
	}
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
    	if(n == 0) return -1;
       node head = new node(0);
       node pre = head;
       node t = null;
       for(int i = 1; i< n; i++)
       {
    	    t = new node(i);
    	   pre.next = t;
    	   pre = t;
       }
       t.next = head;
       node p =t;
       for(int i = 0; i<n-1; i++)
       {
    	   for(int j = 0; j<m-1; j++)
    	   {
    		   p = p.next;
    	   }
    	   p.next = p.next.next;
       }
       return p.num;
    }
}

public class Solution {
    
    // 构造循环链表结构
    public static class Node {
        private int value;
        private Node pre;
        private Node next;
        
        public Node(int value) {
            this.value = value;
            this.pre = null;
            this.next = null;
        }
    }
    
    public int LastRemaining_Solution(int n, int m) {
        if (m == 0 && n == 0) {
            return -1;
        }
        Node head = new Node(0);
        Node cur = head;
        Node last = null;
        for(int i = 1; i < n; i++) {
            last = new Node(i);
            last.pre = cur;
            cur.next = last;
            cur = last;
        }
        cur = head;
        last.next = head;
        head.pre = last;
        int count = n;
        while (count != 1) {
            for (int i = 0; i < m - 1; i++) {
                cur = cur.next;
            }
            cur.pre.next = cur.next;
            cur.next.pre = cur.pre;
            cur = cur.next;
            count--;
        }
        return cur.value;
    }
}

class Solution {
public:
    struct node
    {
        int no;
        node *next;
    };
    int LastRemaining_Solution(int n, int m)
    {
        node *head=new node;
        head->no=n-1;
        head->next=NULL;
        node *tail=head;//保留最后一个位置的节点一边将链表头尾连接
        for(int i=n-2; i>=0; i--)
        {
            node *p=new node;
            p->no=i;
            p->next=head;
            head=p;
        }
        tail->next=head;
        node *pre=tail;//保存被选中的节点前一个以便删去节点后重新连接链表
        while(head->next!=head)//判断条件是链表中只剩一个节点才停下
        {
            node *tmp=head;
            for(int i=0; i<m-1; i++)
            {
                tmp=tmp->next;
                pre=pre->next;
            }
            pre->next=tmp->next;
            head=pre->next;
            delete tmp;
        }
        return pre->no;
    }
};

 class Solution {
public:
    int LastRemaining_Solution(unsigned int n, unsigned int m)
    {
        
        if(n <= 0 && m <= 0) return -1; //蛋疼的特殊条件
        int t = 0;
        for(int i = 2; i <= n; i++)
            t = (t + m) % i;
        return t;
    }
};
/**
约瑟夫问题
递推公式
让f[i]为i个人玩游戏报m退出最后的胜利者的编号，最后的结果自然是f[n]
服了
f[1] = 0;
f[i] = (f[i - 1] + m) mod i;

因为递推，所以可以不用保存状态
代码如下 

*/ 

class Solution {
/*
参考剑指offer,纯手打
定义一个关于m 和n的方程，f(n,m),表示n个数字0,1,2，….n-1;
中每次删除第m个数字最后剩下的数字。
第一个被删除的数字（m-1）%n.
例如0,1,2,3,4,5，删除第3个，即2，那么（3-1）%6=0….2,商0余2，所以2就是那个被删除的数。
在删除第m个数字(定义为k)之后的序列为
0,1,2，…k-1,k+1,…n-1;
在进入下一次循环时删除第m个的时候从第k+1个数开始，这个序列为k+1，，，n-1,0,1,…k-1;函数因此定为f*(n-1,m)
再将这个映射我从0开始的序列，如下：

K+1 → 0；
K+2 → 1;
…
n-1 →  n-1-(k+1)=n-k-2;
0   →  n-k-2+1=n-k-1;
1   →  n-k;
…

k-1 → n-k-1+（k-1）=n-2;
映射p(x)=p(x-k-1)%n;表示映射钱的数字是x,映射后的数字是x-k-1。逆映射为
P*(x)=(x+k+1)%n.
这里记住无论循环多少次删除第m个元素最后剩下的数字是一样的。
有f*(n-1,m)=P*( f(n-1,m))=( f(n-1,m)+k+1)%n.=（f(n-1,m)+m）%n.
因为k=(m-1)%n=(m-1)

*/
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;
        return last;
        
    }
};

    /*
    *这道题我用数组来模拟环，思路还是比较简单，但是各种下标要理清
    */
    public static int findLastNumber(int n,int m){
        if(n<1||m<1) return -1;
        int[] array = new int[n];
        int i = -1,step = 0, count = n;
        while(count>0){   //跳出循环时将最后一个元素也设置为了-1
            i++;          //指向上一个被删除对象的下一个元素。
            if(i>=n) i=0;  //模拟环。
            if(array[i] == -1) continue; //跳过被删除的对象。
            step++;                     //记录已走过的。
            if(step==m) {               //找到待删除的对象。
                array[i]=-1;
                step = 0;
                count--;
            }        
        }
        return i;//返回跳出循环时的i,即最后一个被设置为-1的元素
    }

# -*- coding:utf-8 -*-
class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        childrens = [i for i in range(n)]
        index = 0
        final = -1
        while childrens:
            #k为当前离开的小朋友的下标
            k = (index + (m - 1)) % n
            final = childrens.pop(k)
            #当循环结束时，final指向最后一个小朋友
            n -= 1
            index = k
            #当下标k的元素被删除时，后面的元素向前一步，所以index仍然从k下标开始从后面计算下一个要离开的小朋友
        return final

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;
        }
        return last;         
    }
}; 

java实现
循环队列 时间复杂度N(nm)
import java.util.LinkedList;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        LinkedList<Integer> list=new LinkedList<Integer>();        
        if(m<1||n<1)
            return -1;
        for(int i=0;i<n;i++){
            list.add(i);
        }
        int size=list.size();
        int current=0;
       
        while(list.size()>1){
            list.remove((current+m-1)%size);
            current=(current+m-1)%size;
            size--;            
        }
        return list.remove();
    }
}
约瑟夫 递归公式n=1时，f(n,m)=0;n>1时，f(n,m)=[f(n-1,m)+m]%n;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(n<1||m<1)
            return -1;
        if(n==1)
            return 0;
        else{
            return (LastRemaining_Solution(n-1,m)+m)%n;
        }
    }
}

	public static int LastRemaining_Solution(int n, int m) {
		if(n == 0 || m == 0) {
			return -1;
		}
		int index = 0;
		int size = 0;
		LinkedList<Integer> linkedList = new LinkedList<>();
		for(int i =0; i < n; i++) {
			linkedList.add(i);
		}
		size = linkedList.size();
		while(size > 1) {
			linkedList.remove((index+m-1)%size);
			index = (index+m-1)%size;
			size--;
		}
		return linkedList.get(0);
	}

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

class Solution {
private:
    int josephus(unsigned int n, unsigned int m){
        int s = 0;
        for(int i = 2; i <= n ; i ++)
            s = (s + m)%i;
        return s;
    }
public:
    int LastRemaining_Solution(unsigned int n, unsigned int m)
    {
        if(n == 0) return -1;
        return josephus(n,m);
    }
};

# 笨方法  模拟一遍

# -*- coding:utf-8 -*-
class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        if not n and not m:
            return -1
        nums = list(range(n))
        last = 0
        for _ in range(n-1):
            last = (m+last-1)%len(nums)
            nums.pop(last)
        return nums[0]