@TOC

约瑟夫环问题

约瑟夫环问题
给定一个链表头节点head，和一个正数m
从头开始，每次数到m就杀死当前节点
然后被杀节点的下一个节点从1开始重新数，
周而复始直到只剩一个节点，返回最后的节点

思路

先解决一个问题:
编号和报数之间的关系

有abcd四个人,第一轮的编号是
a:1, b:2 , c:3 , d:4
当淘汰b之后
第二轮的编号就变成
a:3, d:2, c:1

剩一个点的时候存活节点在最后一步的编号中它是编号1
假设有一个公式，传入一个节点淘汰之后的编号,返回淘汰之前的编号
一直调用到一个节点也不淘汰的时候的编号就是幸存者编号
目标就是:推导一个F函数 告诉我淘汰之后的编号怎么对应出淘汰之前的编号

画图像

首先求出一个数字对应的编号
剃刀感觉的图像

根据函数图像的规则:左加右减，上加下减

推出 编号=(数-1)%i+1
给你一个数字报数它减1之后模上i再加1.就得到了它的编号

淘汰之后的编号怎么推淘汰之前的编号
假设i个节点淘汰报数到m的编号
用具体例子

抽象化

延长
限制死定义域

向左移动s位

s是长度i 链表中数到m淘汰人的编号

将刚才算出的编号函数套进去

最后化简到
前=(后+m-1)%i+1

力扣原题:剑指 Offer 62. 圆圈中最后剩下的数字

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public int lastRemaining(int n, int m) {
        return getLive(n,m)-1;
    }
    public int getLive(int n,int m){
        if(n==1){
            return 1;
        }
        return (getLive(n-1,m)+m-1)%n+1;
    }
}

//迭代
    public int lastRemaining(int n, int m) {
        int ans = 1;
        int r = 1;
        while (r <= n) {
            ans = (ans + m - 1) % (r++) + 1;
        }
        return ans - 1;
    }