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

共以下 9 个回答

• 九号球 普通 2023年12月5日 下午8:59

  “`java
  class Solution {
  //有点意思
  public int iceBreakingGame(int num, int target) {
  int f = 0;
  for (int i = 2; i < num + 1; i++) { f = (f + target)%i; } return f; } }

  0 赞同 0 条回复

  登录以回复
• mpweixin用户 永久会员 2023年7月24日 下午11:28

  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 条回复

  登录以回复
• 张开怀 普通 2023年7月24日 下午8:20

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

  时间复杂度：O(n)
  空间复杂度：O(1)

  0 赞同 0 条回复

  登录以回复
• yxy 普通 2023年7月24日 下午7:04

  时间O(n)

  class Solution {
  public:
      int lastRemaining(int n, int m) {
          if(n==1) return 0;
          return (lastRemaining(n-1, m)+m)%n;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 怀瑾 永久会员 2023年7月24日 下午3:25

  “`C++
  public int lastRemaining(int n, int m) {
  // (当前index + m) % 上一轮剩余数字的个数。
  int res = 0;// 最后只剩下一位，坐标肯定是0
  for (int i = 2; i <= n; i++) { res = (res + m) % i; } return res; } ```

  0 赞同 0 条回复

  登录以回复
• Vow the vow。 普通 2023年7月24日 上午11:34

  时间复杂度O(n)

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

  0 赞同 0 条回复

  登录以回复
• 花老爷 普通 2023年7月23日 下午5:39

  动态规划
  时间：O(n)
  空间：O(1)

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

  0 赞同 0 条回复

  登录以回复
• Ming 普通 2023年7月23日 下午4:53

  不太懂

  public int lastRemaining(int n, int m) {
          // (当前index + m) % 上一轮剩余数字的个数。
          int res = 0;// 最后只剩下一位，坐标肯定是0
          for (int i = 2; i <= n; i++) {
              res = (res + m) % i;
          }
          return res;
      }
  

  0 赞同 0 条回复

  登录以回复
• Yodl. 普通 2023年7月23日 下午4:00

  //约瑟夫环/动态规划，思路积累
  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 条回复

  登录以回复