文章目录
约瑟夫环问题
思路
画图像
力扣原题:剑指 Offer 62. 圆圈中最后剩下的数字
约瑟夫环问题
约瑟夫环问题
给定一个链表头节点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;
}
}
1
2
3
4
5
6
7
8
9
10
11
//迭代
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;
}
