题目

描述

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

方法一

思路

创建循环链表，模拟孩子的游戏，每次将第m个孩子淘汰，剩下的最后一个孩子即为赢家。

具体步骤

创建链表类Node，将所给数据转化成循环链表；
模拟游戏运行淘汰孩子，找出最后一个孩子。
参考下图示例：

代码如下

public class Solution {
  // 链表节点
  class Node{
      int val;
      Node next;
      public Node(int val){
          this.val = val;
      }
  }
  // 初始化链表
  private Node init(int n){
      Node head = new Node(0);
      Node p = head;
      for (int i = 1;i < n;++i){
          p.next = new Node(i);
          p = p.next;
      }
      p.next = head;
      return head;
  }

  public int LastRemaining_Solution(int n, int m) {
      // 没有孩子
      if (n == 0 || m == 0){
          return -1;
      }
      if (m == 1){
          return n-1;
      }
      Node head = init(n);
      // 模拟游戏
      for(int i = 0;i < n-1;++i){
          for (int j = 0;j < m-2;++j){
              head = head.next;
          }
          Node p = head.next;
          // 淘汰孩子
          head.next = head.next.next;
          p.next = null;
          head = head.next;
      }
      return head.val;
  }
}

时间复杂度： $O(mn)$ ，双重循环，步数为m，人数为n所以为mn；
空间复杂度：循环链表， $O(n)$ 。

方法二

思路
约瑟夫环问题，最后存在的孩子，即为所需要找的数，那么可以从最后一个元素反过来往前推导。在剩下两个元素的时候，删掉另外一个，然后把它往前移动m个位置。所以当需要复原原本的位置时，就需要在当前位置加m，假设当前位置是index_i，那么还剩两个元素的时候的位置就是index_i-1+m,由于是环，所以index+m可能超过长度n了，所以我们要对其进行取模，它的位置是 (index_i-1+m)%n，这样就形成了递推公式： $index_i = (index_{i-1} + m)\% n$

具体步骤

代码如下；

public class Solution {
  public int LastRemaining_Solution(int n, int m) {
      // 没有孩子
      if (m == 0 || n == 0){
          return -1;
      }
      int res = 0;
      for(int i =2; i <= n; ++i){
          res = (res + m) % i;
      }
      return res;
  }
}

时间复杂度： $O(n)$ ，单层循环；
空间复杂度： $O(1)$ ，常数级空间复杂度。

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

题目

描述

方法一

思路

具体步骤

方法二

思路

具体步骤