[每日一道小算法(六十八)][数学] 孩子们的游戏(圆圈中最后剩下的数)(剑指offer题)

﹏ヽ暗。殇╰゛Y 2023-07-07 12:57 7阅读 0赞

前言:
如果能用数学导出公式,将大大减少我们代码量。

题目描述

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数…这样下去…直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!_)。请你试着想下,哪个小朋友会得到这份礼品呢?(注:小朋友的编号是从0到n-1)

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

解题思路

这道题有两种方法,楼主本人都实现了,一会贴出来代码。
方法一:我们可以一个环链表来模仿这个圈,模仿这个·过程即可完成目标题解。我的实现是使用list,遍历到数组末尾之后再重新从头遍历。模拟这个过程。
方法二:这个就需要我们的数学功底了。需要推导出一个递推公式。我们首先定义一个关于n,m的方程f(n,m),表示每次在n个数字0,1,…,n-1中删除第m个数字最后剩下的数字。在这n个数字中,第一次被删除的数字是(m-1)%n。假设这个数字是k。那么删除k之后剩下的数字为0,1,…,k-1,k+1,n-1。最初序列最后剩下的数字f(n,m) 一定是删除一个数字之后的序列最后剩下的数字,即f(n,m) = f(n-1,m)。
最终我们推出的递推公式为:
在这里插入图片描述

代码样例

方法一 链表模拟

  1. package com.asong.leetcode.ChildrenGame;
  2. import java.util.ArrayList;
  3. import java.util.List;
  4. /** * 孩子们的游戏(圆圈中最后剩下的数) * 思路:使用list模拟环 */
  5. public class Solution1 {
  6. public int LastRemaining_Solution(int n, int m) {
  7. if(n<1||m<1)
  8. {
  9. return -1;
  10. }
  11. List<Integer> list = new ArrayList<Integer>();
  12. for (int i = 0; i < n; i++) {
  13. list.add(i);
  14. }
  15. int cur = -1; //指针
  16. while(list.size()>1)
  17. {
  18. for (int i = 0; i < m; i++) {
  19. cur++;
  20. if(cur==list.size())
  21. {
  22. cur=0;//从头开始
  23. }
  24. }
  25. list.remove(cur);
  26. cur--;//保证移动m个准确性
  27. }
  28. return list.get(0);
  29. }
  30. }

方法二:递推公式

  1. package com.asong.leetcode.ChildrenGame;
  2. /** * 孩子们的游戏(圆圈中最后剩下的数) * 递推公式:f[n]=0; n =1 * f[n]=(f[n-1]+m)%n; (n>1) * */
  3. public class Solution {
  4. public int LastRemaining_Solution(int n, int m) {
  5. if(n<1||m<1)
  6. {
  7. return -1;
  8. }
  9. int res = 0;
  10. for (int i = 2; i <=n; i++) {
  11. res = (res+m)%i;
  12. }
  13. return res;
  14. }
  15. }

发表评论

表情:
评论列表 (有 0 条评论,7人围观)

还没有评论,来说两句吧...

相关阅读