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

Tag: 剑指-Offer Posted on 2022-02-28 09:39:16 Edited on 2022-02-28 10:02:12 Views: 151

概述

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;
    }
};

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