首页 > 试题广场 >

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

[编程题]孩子们的游戏(圆圈中最后剩下的数)

热度指数：416634 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围： $1 \le n \le 5000$ ， $1 \le m \le 10000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

5,3

输出

示例2

输入

2,3

输出

说明

有2个小朋友编号为0，1，第一次报数报到3的是0号小朋友，0号小朋友出圈，1号小朋友得到礼物

示例3

输入

10,17

输出

算法知识视频讲解

牛客题解官

发表于 2020-06-01 16:29:35

精华题解题目的主要信息：从0到n-1（首尾相接）中每次去掉第m个数，下一次从去掉数的下一个开始，直到剩下最后一个数返回的是最后一个数有数为0的特殊情况举一反三：学习完本题的思路你可以解决类似的模拟问题。方法一：递归(推荐使用) 知识点：递归递归是一个过程或函数在其定义或说明中有直接或间接调展开全文

漫漫云天自翱翔

发表于 2021-06-22 10:27:23

精华题解题解一：暴力法解题思路：用数组模拟循环列表，从0开始喊到m个数后，就将其值置为-1。直到数组剩下最后一个数（非-1）。样例如下：复杂度分析：时间复杂度：O(N^2)空间复杂度：O(N)，申请一个数组标记每个小孩子是否退圈 class Solution { public: int Last 展开全文

蒙牛麦片

发表于 2021-06-24 09:28:21

精华题解 JZ46 孩子们的游戏(圆圈中最后剩下的数) 题意分析：这是一个著名问题约瑟夫环问题。示例输入：n=5,m=3返回：3现在有5个小孩，围成一圈，编号从0-4。编号0的孩子从0开始报数，当有小孩报到3-1=2时，该小孩出局。一直到最后剩下的3号小孩。过程图如下：题解一（模拟）：我们使用数展开全文

鸠摩罗什

发表于 2021-07-03 10:57:04

精华题解描述每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m 展开全文

皮卡丘、、、

发表于 2019-09-02 23:53:44

java中直接使用一个list来模拟，并使用一个索引cur类指向删除的位置，当cur的值为list的size，就让cur到头位置。 mport java.util.*; public class Solution { public int LastRemaining_Solution(int 展开全文

Cyril-廖思睿

发表于 2020-01-01 00:44:13

两行代码即可。 public class Solution { public int LastRemaining_Solution(int n, int m) { // 不满足的条件 if (n <= 0 || m <= 0) return -1; retur 展开全文

郭家兴0624

发表于 2019-08-12 09:25:10

题目描述每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意展开全文

中工升达预备毕业生

发表于 2019-12-14 22:07:31

【建议看书上题解】一种方法是用环形链表模拟圆圈的经典解法； class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } publi 展开全文

头都大了

发表于 2020-02-03 16:19:15

题目描述：每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼展开全文

没有offer不改名

发表于 2019-10-07 11:44:39

一开始想到的使用一个链表实现这个功能，当计数到时直接删除那个节点，如此循环，最后一个节点就是幸运星。但是这次我重新思考，觉得使用链表还是太过于复杂，因此我这次使用了一个vector来时，当符合计数条件时，直接移除这个数据，最后vector大小为1的时候，就是找到了幸运星。 class Solutio 展开全文

ccจุ๊บ

发表于 2020-02-16 11:57:24

# -*- coding:utf-8 -*- class Node(): def __init__(self, x): self.val = x self.next = None class Solution: def LastRemaining_S 展开全文

Leno_B

发表于 2022-03-10 10:58:32

class Solution: def LastRemaining_Solution(self , n: int, m: int) -> int: # 烫手山芋, 队列实现删除元素 res_quene = list(range(0, n)) 展开全文

dragonflying

发表于 2020-04-11 20:48:34

孩子们的游戏(圆圈中最后剩下的数) C++11 题目描述：每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m- 展开全文

原来微信名字可以这么长

发表于 2020-01-17 19:24:55

JavaScript三种解法 1.数学公式法（老实讲这个方法我没有仔细研究，参考大神） 2.数组模拟法思路：用一个数组装上小朋友，【0，1，2，3，4，5】，从-1开始计数，直到发现那个小朋友，将它出列，将它后面的小朋友放到队伍前，前面的放在后。重新计数。如 m=4 展开全文

问题信息

基础数学

难度：

916条回答 2880收藏 119784浏览

通过挑战的用户

查看代码

Elastic...

2023-02-13 17:46:26
安布雷拉

2023-02-04 18:54:32
牛客77893...

2022-12-29 13:14:39
牛客74142...

2022-12-24 09:45:33
还在挣扎的螃蟹

2022-12-22 23:43:59

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

输入

输出

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题