NC132 环形链表的约瑟夫问题

题目描述

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。

下一个人继续从 1 开始报数。

n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

1. 暴力解法

没什么好说的，用一个数组模拟整个过程，n-1轮循环，每轮报一次数，然后每次出局的时候剩下的数据向前平移，直到剩一个人。

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int ysf(int n, int m) {
        vector<int> nums(n);
        
        for (int i = 0; i < n; i++) nums[i] = i;
        
        int start = 0; // 数组下标为0的，存的是1号人
        while (nums.size() != 1) {
            // 哪个玩家该出局
            int id_to_away = (start + m - 1) % nums.size();
            
            // 数组中删掉
            nums.erase(nums.begin() + id_to_away);
            
            // 这个人下次开始报1
            start = id_to_away;            
        }
        
        // 题目编号从1开始，代码的下标从0开始，因此加1修正
        return nums[0] + 1;
    }
};

时间复杂度： $O (n^{2})$ , 两重循环。其中erase方法也需要对数组进行一次遍历，故总的复杂度达到了 $O (n^{2})$
空间复杂度： $O (n)$ , 维护了长度为n的数组。

2. 动态规划

方法1的时间复杂度太高了，我们看下有没有规律可以优化。

正向推导似乎很难找到规律，那么正难则反，我们从后往前分析。

设 $f (n, m)$ 为 $n$ 个人玩游戏，报 $m$ 的人退出的游戏，最后剩下的人的编号。我们看看是不是跟 $f (n - 1, m)$ 或 $f (n + 1, m)$ 有关系，如果是的话，就可以dp了。

假设 $f (n, m)$ 已知, 那么我们进行一轮游戏后，从被淘汰的那个人开始，进行游戏 $f (n - 1, m)$ ，应该得到同一个人。

换句话说，我们只要求出游戏 $f (n, m)$ 在第一轮结束后，谁被淘汰，就得到了 $f (n, m)$ 和 $f (n - 1, m)$ 的关系。

第一轮被淘汰的编号显然可以用 $m % n$ 表示，那么我们就得出了动态规划转移式：

f(n,m) = (m\%n + f(n-1,m)) \% n

最终的初始值肯定是 $f (1, m) = 0$ . 因为只有1个人玩游戏的时候，最后剩下的人肯定是0号玩家。

但是这个式子还是比较难算，我们进一步挖掘规律。

f(1, m) = 0 \\ f(2, m) = (f(1, m) + m) \% 2 \\ f(3, m) = (f(2, m) + m) \% 3 \\ ...

发现只要维护前一项就可以，因此我们只需要一个变量维护即可。

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int ysf(int n, int m) {
        // write code here
        int res = 0;
        for(int i=2; i <=n;i++)
        {
            res = (res + m) % i;
        }
        // 题目编号从1开始，代码的下标从0开始，因此加1修正
        return res + 1;
    }
};

时间复杂度： $O (n)$ , 一重循环。
空间复杂度： $O (1)$ , 常数个变量

题解 | #环形链表的约瑟夫问题#

NC132 环形链表的约瑟夫问题

题目描述

1. 暴力解法

2. 动态规划