题解 | #环形链表的约瑟夫问题(进阶)#

约瑟夫问题：
在n个人中（编号为1~n）,从第一个人开始数数，每当计数为m时，此人为A，A自杀踢出；然后下一个从新从1开始计数，当再次数到m时，此人为B，B自杀踢出。当最后剩下一人时结束。

模型等化：将n个人等效为一个环形链表。每次踢出一个人时，链表长度就减小1。

方法一：递归方法
利用递归方法计算存活人在最开始链表中编号。
重点：计算编号
1、每次删除一个人，链表的顺序编号都重新编号（并不是每个节点val重新改变）
例子：

|    次数    |   删除元素    |    顺序编号     |    编号    |
1    X    1~n    1~n
2    i    1~（n-1）    1~(i-1),(i+1)~n 

所以，每次链表的长度为n，计数为m,则删除的为链表头节点之后的s=(m-1)%n+1 个。
2、删除后，某个节点在新链表和旧链表中顺序号不同，发生了变化,

old = (new +s -1)% i +1
  |  其中，i为 旧链表长度;s=(m-1)%i+1
  |
  V
old= (new+m-1)%i+1;

缺点：空间利用过多，导致内存超出限制。

#include<iostream>

using namespace std;

struct list_node{
    int val;
    struct list_node * next;
};
//链表初始化，初始化后已经为环形链表
list_node * input_list(int n)
{
    int  val;
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    for (int i = 1; i <= n; ++i) {
        if (i == 1) {
            cur_pnode->val = i;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = i;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    cur_pnode->next=phead;
    return phead;
}
//计算活下来人的编号
int getLive(int m,int n){
    if(n ==1){
        return 1;
    }
    return (getLive(m, n-1)+ m-1) % n + 1;
}
//该函数是因为利用链表进行计算，虽然结果正确，但是当测试用例长度为5000000，由于开辟空间过大导致空间溢出（不是栈空间溢出）
int JosephusProblem_plus(list_node* head,int m,int n,int tem){
    int tem = getLive(m, n);
    while(--tem){
        head=head->next;
    }
    head->next=head;
    return head->val;
} 

int main(){
    int m=0,n=0;
    scanf("%d", &n);scanf("%d", &m);
     int tem = getLive(m, n);
    //list_node * head = input_list(n);
    //int alive_no =JosephusProblem_plus(head,m,n,tem); 
    //cout<<alive_no<<endl;
    cout<<tem<<endl;
    return 0;
}

方法二：动态规划
等进入动态规划时再回来更新，哈哈