傅禹嘉

题目描述

1. 题目链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
2. 题目内容：
   0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
   例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
   示例 1：

   输入: n = 5, m = 3
   输出: 3

   
   示例 2：

题目解法

1. 解法1：链表（无法AC）

   class Solution {
   class node//链表节点
   {
       int val;
       public node(int value) {
           this.val=value;
       }
       node next;
   }
   public int lastRemaining(int n, int m) {
       if(m==1)return n-1;//一次一个直接返回最后一个即可
       node head=new node(0);
       node team=head;//创建一个链表
       for(int i=1;i<n;i++)
       {
           team.next=new node(i);
           team=team.next;
       }
       team.next=head;//使形成环
       int index=0;//从0开始计数
       while (head.next!=head) {//当剩余节点不止一个的时候
           //如果index=m-2 那就说明下个节点(m-1)该删除了
           if(index==m-2)
           {
               head.next=head.next.next;
               index=0;
           }
           else {
               index++;
           }
           head=head.next;
       }
       return head.val;
   }
   }
   

1. 顺序表法

class Solution {
    public int lastRemaining(int n, int m) {
        List<Integer> list = new ArrayList<>();

        int index=0;
        for(int i=0;i<n;i++)
        {   
            list.add(i);
        }
        index+=m-1;
        while(n>1)
        {

            while(index<n&&n>1)
            {
                list.remove((int)(index));//remove方法的重载
                n--;
                index+=m-1;//往后挪动m位

            }
            index=index%n;//index超出后返回


        }
        return list.get(0);
    }
}

1. dp法
   n个元素的环可以定义为f(n,m)，m表示每次移动的步数。则状态就是f(n,m)。那么对于n-1个元素的环，其最后一个被移除的元素就是f(n-1,m)，则有：

（1）第一个被删除的数为 (m - 1) % n，设下标为k。
（2）假设第二轮的开始元素下标为k+1，那么这n - 1个数构成的约瑟夫环为k + 1, k + 2, k +3, …..,k - 3, k - 2，k-1。做一个简单的映射。
k+1 —> 0
k+2 —> 1
…
n-1 —> n-k-2
0 —> n-k-1
…
k-1 —>n-2
可见，左到右映射关系为p(x)=（x-k-1）%n。因为右边的状态是f(n-1,m)，又因为k=(m-1)%n，

( (np+k=m-1)=>(x-k-1=x-(m-1-np)=x+m))代入上面式中得:f(n,m)

n=1时 f(n,m)=0

n>1时 (f(n−1,m)+m)%n n>1
(f(n,m)+m)%n=f(n-1,m) => f(n,m)=qf(n-1,m)+n-m) => (f(n,m)+(q+1)m-n)%n=(f(n,m)+(q+1)m)%n

class Solution {
    public int lastRemaining(int n, int m) {

 //   if(n<1||m<1)
   //     return -1;

    int last=0; //n=1,最后移出环的元素
    for(int i=2;i<=n;++i)
        last=(last+m)%i;
    return last;

    }
}