关于java:JZ046圆圈中最后剩下的数

41次阅读

共计 1205 个字符，预计需要花费 4 分钟才能阅读完成。

每年六一儿童节, 牛客都会筹备一些小礼物去探访孤儿院的小朋友, 往年亦是如此。HF 作为牛客的资深元老, 天然也筹备了一些小游戏。

其中, 有个游戏是这样的: 首先, 让小朋友们围成一个大圈。而后, 他随机指定一个数 m, 让编号为 0 的小朋友开始报数。

每次喊到 m - 1 的那个小朋友要入列唱首歌, 而后能够在礼品箱中任意的筛选礼物, 并且不再回到圈中,

从他的下一个小朋友开始, 持续 0 …m- 1 报数 …. 这样上来 …. 直到剩下最初一个小朋友, 能够不必表演, 并且拿到牛客名贵的“名侦探柯南”典藏版 (名额有限哦!!^_^)。

请你试着想下, 哪个小朋友会失去这份礼品呢？(注：小朋友的编号是从 0 到 n -1)

如果没有小朋友，请返回 -1

题目链接 : 圆圈中最初剩下的数

/**
 * 题目：圆圈中最初剩下的数
 * 题目形容
 * 每年六一儿童节, 牛客都会筹备一些小礼物去探访孤儿院的小朋友, 往年亦是如此。HF 作为牛客的资深元老, 天然也筹备了一些小游戏。* 其中, 有个游戏是这样的: 首先, 让小朋友们围成一个大圈。而后, 他随机指定一个数 m, 让编号为 0 的小朋友开始报数。* 每次喊到 m - 1 的那个小朋友要入列唱首歌, 而后能够在礼品箱中任意的筛选礼物, 并且不再回到圈中,
 * 从他的下一个小朋友开始, 持续 0...m- 1 报数.... 这样上来.... 直到剩下最初一个小朋友, 能够不必表演, 并且拿到牛客名贵的“名侦探柯南”典藏版 (名额有限哦!!^_^)。* 请你试着想下, 哪个小朋友会失去这份礼品呢？(注：小朋友的编号是从 0 到 n -1)
 * <p>
 * 如果没有小朋友，请返回 -1
 * 题目链接：* https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6?tpId=13&&tqId=11199&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
 */
public class Jz46 {

    /**
     * 约瑟夫环，圆圈长度为 n 的解能够看成长度为 n-1 的解再加上报数的长度 m。因为是圆圈，所以最初须要对 n 取余。*
     * @param n
     * @param m
     * @return
     */
    public int lastRemaining_Solution(int n, int m) {if (n == 0) {return -1;}
        if (n == 1) {return 0;}
        return (lastRemaining_Solution(n - 1, m) + m) % n;
    }

    public static void main(String[] args) {Jz46 jz46 = new Jz46();
        System.out.println(jz46.lastRemaining_Solution(4, 6));
    }
}