【杂题】剑指 Offer 62. 圆圈中最后剩下的数字

共以下 5 个回答

• 王位詮釋 普通 2024年4月14日 下午9:05

  数学+迭代法：
  class Solution {
      public int iceBreakingGame(int num, int target) {
          int x = 0;
          for (int i = 2; i <= num; i++) {
              x = (x + target) % i;
          }
          return x;
      }
  }
  

  链表法，模拟删除，但是后面会超时：
  class Solution {
      public int iceBreakingGame(int num, int target) {
          Node pre = new Node();
          Node cur = pre;
          //构造环形数组
          for(int i=0;i<num;i++){
              cur.next = new Node(i,null);
              cur = cur.next;
          }
          cur.next = pre.next;//现在cur指向的是最后一个元素
          cur = cur.next;//此时cur指向第一个元素
          while(cur.next!=cur){
              int count = 1;
              while(count<target){
                  cur = cur.next;//往后走一步
                  count++;
              }
              //把cur所指向的节点删除
              cur.val = cur.next.val;
              cur.next = cur.next.next;
          }
          return cur.val;
      }
  }
  class Node{
      int val;
      Node next;
      public Node(){
  
      }
      public Node(int val,Node next){
          this.val = val;
          this.next = next;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 紫芝 普通 2024年4月12日 上午9:19

  思路：约瑟夫环

  func iceBreakingGame(num int, target int) int {
      old := 0
      for i:=2; i<=num; i++ {
          old = (old + target) % i
      }
      return old
  }
  

  0 赞同 0 条回复

  登录以回复
• 云无深雁影 普通 2024年4月10日 下午11:49

  class Solution {
  public int iceBreakingGame(int num, int target) {
  List list = new ArrayList<>();
  for(int i = 0; i < num; i++)
  list.add(i);
  int current = 0;
  for(int i = 0; i < num – 1; i++){
  current = (current + target -1) % list.size();
  list.remove(current);
  }
  return list.get(0);
  }
  }//空间On2
  //时间On
  //链表解法

  class Solution {
  public int iceBreakingGame(int num, int target) {
  int ans = 0;
  for(int i = 2; i <= num; i++){
  ans = (ans + target) % i;
  }
  return ans;
  }
  }//数学解法

  0 赞同 0 条回复

  登录以回复
• 白雪公主倒拔垂杨柳 永久会员 2024年4月9日 下午8:08

  class Solution {
      public int iceBreakingGame(int num, int target) {
          return f(num,target);
  
      }
  
      // 返回值为最后留下的元素的号码
      public int f(int num,int target){
          // 退出递归的条件
          if(num==1) return 0;
  
          // 关系：长度为num的序列删除了一个后成为长度为 num -1的序列
  
          int x = f(num-1,target);
  
           return (target + x) % num;
      }
  }
  

  时间复杂度：O(num)

  空间复杂度：O(num)

  0 赞同 0 条回复

  登录以回复
• Jimmy 普通 2024年4月8日 下午10:40

  最终剩下一个人时的安全位置肯定为0，反推安全位置在人数为n时的编号
  人数为1： 0
  人数为2： (0+m) % 2
  人数为3： ((0+m) % 2 + m) % 3
  人数为4： (((0+m) % 2 + m) % 3 + m) % 4
  ……..
  迭代推理到n就可以得出答案

  class Solution {
  public:
      int lastRemaining(int n, int m) {
          int result = 0;
          for (int i = 2; i <= n; ++i) {
              result = (result + m) % i;
          }
          return result;
      }
  };
  

  0 赞同 0 条回复

  登录以回复