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

传送门

nowcoder
leetcode

题目描述

首先，n 个人围成一个大圈，编号是 0~n-1。
然后，随机指定一个数 m ，让编号为 0 的人开始报数。
每次喊到 m-1 的人出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中。
从下一个人开始，继续 0…m-1 报数。
这样下去，直到剩下最后一个人，可以不用表演，并且拿到典藏版礼物。

C++ 代码 - nowcoder

/*
    迭代实现

    最后只剩下一个元素，假设最后的这一个元素为 num, 该元素最终的下标一定是 0。
    反推过程：
        (当前index + m) % 上一轮剩余的个数
*/
public:
    int LastRemaining_Solution(int n, int m) {
        if (n <= 0 || m < 0) return -1;

        int res = 0;
        // 最后一轮剩下2个人，开始反推
        for (int i = 2; i <= n; i ++) {
            res = (res + m) % i;
        }
        return res;
    }
};

/*
    递归实现
    
    圆圈长度为 n 的解可以作为长度为 n-1 的解再加上报数的长度 m。
    因为是圆，最后需要对 n 取余。
*/
class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        if (n == 0) return -1;
        if (n == 1) return 0;

        return (LastRemaining_Solution(n - 1, m) + m) % n;
    }
};

C++ 代码 - leetcode

/*
    迭代实现
    
    最后只剩下一个元素，假设最后的这一个元素为 num, 该元素最终的下标一定是 0。
    反推过程：
        (当前index + m) % 上一轮剩余的个数
*/
class Solution {
public:
    int iceBreakingGame(int n, int m) {
        if (n <= 0 || m < 0) return -1;

        int res = 0;
        // 最后一轮剩下2个人，开始反推
        for (int i = 2; i <= n; i ++) {
            res = (res + m) % i;
        }
        return res;
    }
};