Galaxy

Appearance

LCR.187 破冰游戏 ​

剑指 offer 62. 圆圈中最后剩下的数字

社团共有 num 位成员参与破冰游戏，编号为 0 ~ num-1。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字 target，从 0 号成员起开始计数，排在第 target 位的成员离开圆桌，且成员离开后从下一个成员开始计数。请返回游戏结束时最后一位成员的编号。

示例 1：

text
输入：num = 7, target = 4
输出：1

示例 2：

text
输入：num = 12, target = 5
输出：0

提示：

  • 1 <= num <= 10^5
  • 1 <= target <= 10^6

解题思路 ​

实现 ​

数学 + 迭代 ​

js
/**
 * @param {number} num
 * @param {number} target
 * @return {number}
 */
var iceBreakingGame = function (num, target) {
  let res = 0;
  for (let i = 2; i <= num; i++) {
    res = (res + target) % i;
  }
  return res;
};

数学 + 递归 ​

js
/**
 * @param {number} num
 * @param {number} target
 * @return {number}
 */
var iceBreakingGame = function (num, target) {
  const dfs = (n, m) => {
    if (n === 1) return 0;
    let x = dfs(n - 1, m);
    return (m + x) % n;
  };
  return dfs(num, target);
};