题目
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。 其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那 个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这 样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪 个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
分析1
从当前节点开始数，数到第m个就输出，如果数到最后还没有到m,就又回到链表头继续数。找到之后，删除当前链表的节点，并把指针前移一位。
代码1
import java.util.ArrayList;
public class Solution {
public int LastRemaining_Solution(int n, int m) {
// 这就是约瑟夫环
if(n < 1 || m <1){
return -1;
}
// 创建一个链表用于存储小孩
ArrayList<Integer> children = new ArrayList<>();
// 存入小孩
for(int i = 0; i < n;i++){
children.add(i);
}
// 当前读取到的下标
int index = -1;
// 结果
int result= -1;
// 移动的步数
int step = 0;
// 循环输出小孩
while(children.size() > 0){
index ++;
// 如果读取到最后一位，就要从头开始读
if(index == children.size())
index = 0;
//步数增加之后判断
step ++;
if(step == m){
result = children.get(index);
children.remove(index);
// 指向当前元素的前一个
index -=1;
// 步长变为0
step = 0;
}
}
return result;
}
}
分析2
上面的方法简介，也很容易理解，但是会重读的去遍历链表，因此不是时间复杂度O(m)最优的。
要想一次遍历，就输出正确结果，需要用到数学推倒，当然这肯定不是我想出来的。
由题目可知，下标是0，1，2…n-1.
第一个出局的小孩是(m-1)%n.
下一个出局的小孩，从（m-1）%n + 1，开始进行计算。
假如第一个出局的小孩的下标是k,那么下一趟开始记数的序列是 k+1,K+2,k+3……n-1,0,1,2……k-1.
这个数列的0的位置是k+1,最后k-1的位置是n-1.
我们很容易找出对应关系，不需要去归纳总结，只需要举例就行了。
k+1 —> 0 k+2 -> 1 . . . n-1 -> n-k-2 0 -> n-k-1 . . . k-1 -> n-2
从k+1到n-1，都很好总结，p(x) = x-k-1;
但是当x=0的时候，这个方法不行了，所以我们要进行取模。
也就是p(x) = （x-k-1）% n
由此，得到了一个映射关系。
这个映射的反映射是：
p^(x) = (x+k+1)%n
用f(n,m)表示从(0~n-1)开始删除后的最终结果。
用q(n-1,m)表示从(k+1,…,n-1,0,1,…k-1)开始删除后的最终结果。
最终这两个函数的结果一定是想用的。
也就是最后一个数一定是一样的，则f(n,m)=q(n-1,m)。
把n个人的编号改为0~n-1，然后对删除的过程进行分析。 第一个删除的数字是(m-1)%n，几位k，则剩余的编号为(0,1,…,k-1,k+1,…,n-1)，下次开始删除时，顺序为(k+1,…,n-1,0,1,…k-1)。
则f(n,m)=q(n-1,m)=p^(f(n-1,m))=(f(n-1,m)+k+1)%n，又因为k=(m-1)%n。
f(n,m)=(f(n-1,m)+m)%n;
最终的递推关系式为
f(1,m) = 0; (n=1)
f(n,m)=(f(n-1,m)+m)%n; （n>1）
还有一种更为简洁的理解：
f(1)=0;
当n很大时，计数的基数应该使用从上一个数的后面一个开始数m个，f(2) = f(1) + m
所以，递推公式是：f(n) = f(n-1) + m.
由于，m可能会超过人数，因此要取余。
最终的递推公式是：f(n) = (f(n-1)+m)%n。
代码2
// 分析过程求出规律：递归
public int LastRemaining_Solution2(int n, int m){
if (n<=0 || m<= 0) {
return -1;
}
if(n == 1){
return 0;
}
return (LastRemaining_Solution2(n-1, m) + m)%n;
}
递推的过程是n从大到小.
而循环的过程是n从小开始，代码如下：
// 分析过程求出规律：循环
public int LastRemaining_Solution3(int n, int m){
if (n<=0 || m<= 0)
return -1;
int result = 0;
for(int i =2;i<=n;i++){
result = (result + m)%i;
}
return result;
}
测试代码
import java.util.ArrayList;
import javax.print.attribute.standard.ReferenceUriSchemesSupported;
public class offer45 {
public static void main(String[] args) {
offer45 offer455 = new offer45();
System.out.println(offer455.LastRemaining_Solution(5, 3));
System.out.println(offer455.LastRemaining_Solution2(5, 3));
System.out.println(offer455.LastRemaining_Solution3(5, 3));
}
// 方法一：根据规则模拟过程
public int LastRemaining_Solution(int n, int m) {
if (n<=0 || m <=0 ) {
return -1;
}
ArrayList< Integer> list = new ArrayList<>();
for(int i = 0; i < n; i++){
list.add(i);
}
// 移动的步数
int step = 0;
// 链表对应的下标
int index = -1;
// 记录最终记过
int result = -1;
while(list.size() > 0){
index++;
if (index == list.size() ) {
index = 0;
}
step++;
if (step == m) {
result = list.get(index);
list.remove(index);
index--;
step = 0;
}
}
return result;
}
// 分析过程求出规律：递归
public int LastRemaining_Solution2(int n, int m){
if (n<=0 || m<= 0) {
return -1;
}
if(n == 1){
return 0;
}
return (LastRemaining_Solution2(n-1, m) + m)%n;
}
// 分析过程求出规律：循环
public int LastRemaining_Solution3(int n, int m){
if (n<=0 || m<= 0)
return -1;
int result = 0;
for(int i =2;i<=n;i++){
result = (result + m)%i;
}
return result;
}
}
