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

共以下 8 个回答

• hi 普通 2023年12月30日 下午5:50

  1. f(n) 为n 个人玩所得剩下的人的下标与f(n-1）所得的结果有target 的关系（前提是n – 1 那个环的编号是满足条件的）

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

  0 赞同 0 条回复

  登录以回复
• June 普通 2023年11月23日 下午5:06

  class Solution {
      public int iceBreakingGame(int num, int target) {
          if( num == 0) return num;
          //return (lastRemaining(n - 1, m) + m) % n;
          // 优化
          int res = 0;
  
          for(int i = 1; i <= num; i++){
              res = (res + target) % i;
          }
          return res;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• Marshan 普通 2023年9月11日 下午4:03

  模拟会超时

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

  0 赞同 0 条回复

  登录以回复
• Mby 普通 2023年8月22日 下午2:22

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

  0 赞同 0 条回复

  登录以回复
• 阿尚 普通 2023年8月12日 下午8:37

  //递归
  class Solution {
      public int lastRemaining(int n, int m) {
          if(n == 1) return 0;
          return (lastRemaining(n - 1, m) + m) % n;
      }
  }
  
  //迭代
  class Solution {
      public int lastRemaining(int n, int m) {
          int x = 0; //最终剩余的数的初始位置一定是0，反推其最开始的位置
          for (int i = 2; i <= n; i++) {
              x = (x + m) % i; //递推公式f(n, m) = [f(n−1, m) + m] % n
          }
          return x;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 长河呼叫黄江 普通 2023年8月12日 下午3:26

  8.10 周四
  Day31：下面是代码

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

  0 赞同 0 条回复

  登录以回复
• NullPointerException 普通 2023年8月11日 下午3:06

  class Solution {
  public int lastRemaining(int n, int m) {
  // 从左往右选 到m个 最后吧m+1放首位 不就是把m+1往左移m个到头吗
  //所以 从下轮回到最开始 不就是补回被删的m 再右移回去
  //f(n)=(f(n-1)+m)%n
  int dp[]=new int[n+1];
  dp[0]=0;
  if(n1) return 0; //从0开始 最后一定为0
  for(int i=2;i<=n;i++)
  {
  dp[i]=(dp[i-1]+m)%i;
  }
  return dp[n];
  }
  }

  0 赞同 0 条回复

  登录以回复
• AD钙奶 普通 2023年8月11日 下午2:48

  约瑟夫环

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

  0 赞同 0 条回复

  登录以回复