JZ62 孩子们的游戏(圆圈中最后剩下的数)
JZ62 孩子们的游戏(圆圈中最后剩下的数)
- 题目
- 题解(138)
- 讨论(914)
- 排行
- 面经
new
中等 通过率：33.14% 时间限制：1秒 空间限制：256M
知识点基础数学
描述
每年六一儿童节，牛客都会准备一些小礼物和小游戏去看望孤儿院的孩子们。其中，有个游戏是这样的：首先，让 n 个小朋友们围成一个大圈，小朋友们的编号是0~n-1。然后，随机指定一个数 m ，让编号为0的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续0... m-1报数....这样下去....直到剩下最后一个小朋友，可以不用表演，并且拿到牛客礼品，请你试着想下，哪个小朋友会得到这份礼品呢？
数据范围：1≤𝑛≤50001≤n≤5000，1≤𝑚≤100001≤m≤10000
要求：空间复杂度 𝑂(1)O(1)，时间复杂度 𝑂(𝑛)O(n)
思路：
方法一是用链表模拟每一次到然后退出的过程，最后看剩下哪一个号。
方法二是递归的做法，规定dp数组，i表示有i个人的时候，最后剩下的数字。找dp[i]和dp[i-1]的关系。
因此，当dp[i-1]的值i-m到i-1的时候，dp[i]=dp[i-1]-(i-m),当dp[i-1]的值在0到i-1-m时，dp[i]=dp[i-1]+m.
因此只需要进行递归就可以的出dp[n]也就是所要求的结果。
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param n int整型 * @param m int整型 * @return int整型*/struct ListNode{int val;ListNode*next;};int LastRemaining_Solution(int n, int m) {// // write code here// ListNode *head=new ListNode;// ListNode*pre=head;// head->val=0;// for(int i=1;i<n;i++)// {// ListNode*cur=new ListNode;// cur->val=i;// pre->next=cur;// pre=cur;// }// pre->next=head;// ListNode*curnode=head;// // for(int i=0;i<=n;i++)// // {// // cout<<curnode->val;// // curnode=curnode->next;// // }// while(--n)// {// for(int i=0;i<m-1;i++)// {// curnode=curnode->next;// pre=pre->next;// }// curnode=curnode->next;// pre->next=curnode;// }// return pre->val;vector<int>dp(n+1);dp[1]=0;for(int i=2;i<=n;i++){ int m1=m;m1%=i;if(dp[i-1]<=(i-m1-1)%i){dp[i]=dp[i-1]+m1;}else {dp[i]=dp[i-1]-(i-m1);}}return dp[n];}
};