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

概述

https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/

简单题并不简单啊淦。

暴力法

超时的解，实现的时候注意一点：if (step == 0) step = m; 取余可以，但是如果为 0 的话需要置回。

class Solution {
public:
    int lastRemaining(int n, int m) {
        vector<bool> nums(n, true);
        int c = 0;
        int r = n;
        while (r > 0) {
            int step = m % r;
            if (step == 0) step = m;
            while (true) {
                if (nums[c]) {
                    step --;
                    if (step == 0) break;
                }
                c ++;
                c %= n;
            }
            nums[c] = false;
            r --;
        }
        return c;
    }
};

递推解

对于问题 n m 的解，我们第一步剔除掉第 m 个数，然后求问题 (n-1) m 的解，注意这里起始点变了，因此需要做适当的偏移。

形式化描述为：f(n, m) = (f(n - 1, m) + m) % n（不要对 m 取余！）

递归解：

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 ans = 0;
        for (int i = 2; i <= n; i ++) {  // i is "n"
            ans = (ans + m) % i;
        }
        return ans;
    }
};

Links: sword-offer-62

未经允许，禁止转载，本文源站链接：https://iamazing.cn/