JZ62 孩子们的游戏(圆圈中最后剩下的数)

题目

每年六一儿童节,牛客都会准备一些小礼物和小游戏去看望孤儿院的孩子们。
其中,有个游戏是这样的:首先,让 n 个小朋友们围成一个大圈,小朋友们的编号是0~n-1。
然后,随机指定一个数m,让编号为0的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌,
然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,
继续0... m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客礼品,请你试着想下,
哪个小朋友会得到这份礼品呢?

方法1 暴力算法

思路

算法实现

用数组模拟循环列表,从0开始喊到m个数后,就将其值置为-1。直到数组剩下最后一个数(非-1)。

代码

package mid.JZ62孩子们的游戏;
import java.util.ArrayList;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if (m == 0) return -1;
        int num = 0, k = 0;
        int[] child = new int[n];
        for (int i = 0; k != n - 1; i = (++i) % n) {//i=(++i) % n这里是一个特殊操作,使遍历自动再数组内循环。
            if (child[i] == 0) {
                num++;
                if (num == m) {
                    num = 0;
                    child[i] = 1;
                    k++;
                }//此位置小孩退圈
            }
        }
        for (int i = 0; i < child.length; i++) {
            if (child[i] == 0) {
                return i;
            }
        }
        return -1;
    }
}

方法2 约瑟夫问题递推公式

思路

算法实现
利用约瑟夫问题的递推公式 f(n,m) = ( f(n-1,m) +m)%n )
重新编号之前 m, m+1,m+2,....重新编号之后 0 ,1 ,2,....

代码

package mid.JZ62孩子们的游戏;
import java.util.ArrayList;
public class Solution {
    public int LastRemaining_Solution(int n, int m) {
            if(n <= 0) return -1;
            return (LastRemaining_Solution(n-1,m)+m)%n;
        }
}
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。