0%

LeetCode 820.单词的压缩编码

发表于 分类于 Valine：

题目描述

约瑟夫环问题

标准做法 递归 $O(n)$

由于问题是求0到n-1里最后剩下的数字，所以问题也可以转换为安全数字的序号。对问题建模，令f(n, m)为问题的答案，即最终安全位置的序号。最开始，我们要删除的是第m%n个元素，之后，序列长度变为n-1，然后从第m%n位开始往后数。剩下的n-1长度的序列从第m%n位开始，只要往后数f(n-1, m)位就能达到安全位置，所以(m%n+f(n-1,m))%n即为所求。(m%n+f(n-1,m))%n = (m+f(n-1, m)%n

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    int f(int n, int m) {
        if (n == 1)
            return 0;
        int x = f(n - 1, m);
        return (m + x) % n;
    }
public:
    int lastRemaining(int n, int m) {
        return f(n, m);
    }
};

标准做法 迭代/DP $O(n)$

由上面的递归式，就可以得到DP所需的状态转移方程

只有一个状态转换量，所以可以用简单变量替代

在i=1时，也就是长度为1的序列，安全位置就是0，即f1 = 0

1
2
3
4
5
6
7
8
9
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;
    }
};

总结

  • 模拟约瑟夫环的删除过程会超时
  • 这种类似归纳法解决问题的逻辑很巧妙，希望能掌握下来

参考

坚持原创技术分享，您的支持将鼓励我继续创作！

欢迎关注我的其它发布渠道