每日OJ题_牛客_孩子们的游戏_约瑟夫环_C++_Java
目录
牛客_孩子们的游戏_约瑟夫环
描述：
每年六一儿童节，牛客都会准备一些小礼物和小游戏去看望孤儿院的孩子们。其中，有个游戏是这样的：首先，让 n 个小朋友们围成一个大圈，小朋友们的编号是0~n-1。然后，随机指定一个数 m ，让编号为0的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续0... m-1报数....这样下去....直到剩下最后一个小朋友，可以不用表演，并且拿到牛客礼品，请你试着想下，哪个小朋友会得到这份礼品呢？
题目解析
- 解法1：模拟。用数组或者链表模拟均可。但是数据量大的话会超时。
- 解法2：数学规律。通过画图可以找到相邻两次删除坐标的规律。通过递推关系，求出剩下的最后一个数是哪个。
C++代码
class Solution
{
public:
int LastRemaining_Solution(int n, int m)
{
int f = 0;
for(int i = 2; i <= n; i++) f = (f + m) % i;
return f;
}
};Java代码
import java.util.*;
public class Solution
{
public int LastRemaining_Solution (int n, int m)
{
int f = 0;
for(int i = 2; i <= n; i++) f = (f + m) % i;
return f;
}
}原文地址：https://blog.csdn.net/GRrtx/article/details/142496318
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！