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

共以下 4 个回答

• 陆狗陆狗 普通 2025年1月7日 上午10:32

  解题思路
  – dp[n] 和 dp[n-1]的关系是什么？dp[n] 表示的是i个数据，dp[n-1]表示的i-1个数据
  – 那么只需要dp[n]先把第一轮要去除的数据去除掉，去除后的规模就和dp[n-1]保持一致了
  – 去除的点index= (m-1)%n，dp[n-1]’的起点是index= m % n。注意dp[n]=dp[n-1]‘
  – 如果我们把dp[n-1]’的起点index= m % n视同是0，dp[n-1]‘=( m%n + dp[n-1] ) ,因为可能越界，dp[n-1]‘=( m%n + dp[n-1] ) % n=dp[n]
  【题解1】

  class Solution {
      public int iceBreakingGame(int num, int target) {
          // dp[n] 和 dp[n-1]的关系是什么？dp[n] 表示的是i个数据，dp[n-1]表示的i-1个数据
          // 那么只需要dp[n]先把第一轮要去除的数据去除掉，去除后的规模就和dp[n-1]保持一致了
          // 去除的点index= (m-1)%n，dp[n-1]’的起点是index= m % n。注意dp[n]=dp[n-1]‘
          // 如果我们把dp[n-1]'的起点index= m % n视同是0，dp[n-1]‘=( m%n + dp[n-1] ) ,因为可能越界，
          // dp[n-1]‘=( m%n + dp[n-1] ) % n=dp[n]
          // 【错误】index要从0开始计数
          int[] dp = new int[num + 1];
          dp[1] = 0;
          for (int i = 2; i <= num; i++) {
              // 【错误】n是会变动的，就是这里的i
              dp[i] = (target % i + dp[i - 1]) % i;
          }
          return dp[num];
      }
  }
  

  • 错误点1：index要从0开始计数
  • 错误点2：n是会变动的，就是这里的i

  0 赞同 0 条回复

  登录以回复
• 秋山丽奈 普通 2024年12月30日 下午8:39

  class Solution {
      public int iceBreakingGame(int n, int m) {
          int ans = 0;
          // 最后一轮剩下2个人，所以从2开始反推
          for (int i = 2; i <= n; i++) {
              ans = (ans + m) % i;
          }
          return ans;
      }
  }
  
  

  0 赞同 0 条回复

  登录以回复
• Aatorx 永久会员 2024年12月30日 下午2:39

  class Solution {
  public:
      int iceBreakingGame(int num, int target) {
          int res = 0;
          for(int i = 2; i <= num; i++) {
              res = (res + target) % i;
          }
          return res;
      }
  };
  

  时间复杂度O(N)，空间复杂度O(1)。

  0 赞同 0 条回复

  登录以回复
• 晓宇 普通 2024年12月28日 下午5:35

  class Solution {
  public:
      int iceBreakingGame(int num, int target) {
          // 每次淘汰后，重新计算环中剩余人数时的 新起始索引 new_idx = (old_idx + tar) % n
          if(num == 0) return num;
          return (iceBreakingGame(num - 1,target) + target) % num;
          // o(n) o(1)
      }
  };
  
  class Solution {
  public:
      int iceBreakingGame(int num, int target) {
          // 每次淘汰前，重新计算环中淘汰前人数时的 新起始索引 new_idx = (old_idx + tar) % n
          int res = 0; // 初始索引
          for (int i = 2; i <= num; i++) { 
              res = (res + target) % i; 
          }
          return res; 
          // on o1
      }
  };
  /*****循环链表*****/
  struct Node{
      int val;// 节点的值（编号）
      Node *next;  // 指向下一个节点
      Node (int x) : val(x) , next(nullptr){}
  };
  
  class Solution {
  public:
      int iceBreakingGame(int num, int target) {
          if(num <= 1) return 0;
          if(target == 1) return num - 1;
          // 创建循环链表
          Node *head = new Node(0);
          Node *p = head;
          for(int i = 1; i < num;i++){
              Node *node = new Node(i);
              p->next = node;
              p = p->next;
          }
          p->next = head;
          // 逐一搜索
          Node *cur = head;
          while(cur->next != cur){
  
  
              for(int i = 1;i < target - 1;i++){ // 注意是从当前开始数
                  cur = cur->next;
              }
              // 移除节点
              Node *toDelete = cur->next;
              cur->next = cur->next->next;
              delete toDelete;
  
              cur = cur->next;
  
          }
          int res = cur->val;
          delete cur;
          return res;
          // o(n^2) o(n)
      }
  };
  

  0 赞同 0 条回复

  登录以回复