约瑟夫环问题

约瑟夫环是一个经典的算法题，总是忘记其解法，今天写篇博客记录下，方便复习同时加深印象！

LeetCode 剑指Offer 62

这里以LeetCode 剑指 Offer 62题为例，讲解下约瑟夫环问题的解决思路（[Leetcode主站 1823](1823. 找出游戏的获胜者)也是同样的问题）。

题目描述如下：

“0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。”

解法分析：

假设$n = 7$，$m$为任意值，用一个数组$arr = [0,1,2,3,4,5,6]$表示原始7个数字，我们用$f(7,m)$表示每次删除数组$arr=[0,1,...,7]$第m个数，最终能保留下来的数字下标。下面展开我们的分析：

• 根据题目描述，第一次被删除的数字是$arr[m\%7-1]$。

• 假设$m\%7=4$，那么删除一次后得到的新数组为（3被删除从4开始）：$arr'=[4,5,6,0,1,2]$。

• 根据前面的定义，对于$arr'$，每次删除第m个数，最终保留下来的的数应该是$arr'[f(6, m)]$。

• 稍加分析我们就能发现：$arr'[f(6,m)]$对应$arr$中的元素下标，就是我们需要的结果$f(7,m)$。不难发现$arr$和$arr'$之间元素的映射关系为：$arr'[0]=arr[(m\%7-1+1)\%7], arr'[1]=arr[(m\%7-1+2)\%7],...,arr'[5]=arr[(m\%7-1+6)\%7]$，即$arr'[i]=arr[(m+i)\%7]$

• 也就是说$arr'[f(6,m)]=arr[(m+f(6,m))\%7]=arr[f(7,m)]$，即$f(7,m)=(m+f(6,m))\%7$，这显然是一个迭代公式，我们可以通过递归来求解该问题。

用$n$代替上述公式中的$7$，我们就可以得到一个该问题的递推通解：$f(n,m)=(m+f(n-1,m))\%n$，$f(n,m)$表示0~n-1个数字，每次删除第m个数字，最终剩余的那个数字。对于这个问题，我们可以使用递归或者迭代求解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    //迭代
    public int lastRemaining(int n, int m) {
        //f(n, m) = (m + f(n-1, m)) % n;
        int res = 0;
        for(int i = 2; i <= n; ++i)
            res = (m + res) % i;
        return res;
    }
    //递归
    public int lastRemaining2(int n, int m) {
        if(n == 1) return 0;
        return (m + lastRemaining2(n-1, m)) % n;
    }
}

总结： 约瑟夫环问题解法的思想其实类似于动态规划，将大规模（n）问题，变成小规模（n-1）子问题，用子问题的解来反推规模更大的父问题的解。

LeetCode 390

这一题和约瑟夫环问题不太一样，但是两者思想是差不多的，都可以找迭代公式，将大规模问题转换成规模更小的子问题。

题目描述如下：

列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：

• 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
• 重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
• 不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。

给你整数 n ，返回 arr 最后剩下的数字。

解法一：

第一种解法和约瑟夫环没太大关联。我们先看下图这个示例：

稍加观察我们不难发现：

1. 每一轮删除元素后，剩余的所有元素构成了一个等差数列，并且公差分别是1、2、4。假设用step表示公差，每删除一轮，等差数列的公差变大一倍，即step *= 2。

2. 用len表示数组大小，每轮删除后，数组大小都变成原来一半（向下取整），即len /= 2。

3. 用first表示第一个元素的值，count表示轮数（从0开始），每轮删除，first更新规则如下：

   • 当count为偶数时，从左往右删除

     • 无论len为奇数还是偶数，数组第一个元素都会被删除

       first += step

   • 当count为奇数时，从右往左删除

     • 当len为奇数时，两端元素都被删除，作如下更新

       first += step

     • 当len为偶数时，第一个元素被保留，最后一个元素被删除

       first = first

我们不断重复上述过程，直到数组大小为1，就找到了最终的答案。

将上述分析用代码表示出来，即为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int lastRemaining(int n) {
        int len = n， first = 1， count = 0， step = 1;
        while(left > 1){
            if(count % 2 == 0){//偶数，从左往右删除
                first += step;
            }else{//奇数，从右往左删除
                if(len % 2 == 1)
                    first += step;
            }
            step = step << 1;
            len >>= 1;
            count++;
        }
        return first;
    }
}

解法二：

这种解法的思想就和约瑟夫环问题很像，先找到递推公式，用更小规模的子问题来反推大规模问题的解。

• 假设$f(i)$表示在$1\sim i$中进行[从左到右，从右到左]轮流删除后最终剩余的编号；

• 假设$f'(i)$表示在$1\sim~i$中进行[从右到左，从左到右]轮流删除后最终剩余的编号。

  • 这个其实等价于在$i\sim 1$中进行[从左到右，从右到左]轮流删除后最终剩余的编号。

  • 稍加分析我们不难发现：$f(i)+f'(i)=i+1$，因为两者是对称关系。

现在假设其实序列为$arr=[1,2,...,i]$，我们从左往右删除一次后，得到的新序列应该是$arr'=[2,4,6,...,x]$。

其中根据$i$奇偶性不同，$x$的值为$i$或$i-1$，并且新序列的长度是$i/2$（原长度的一半向下取余）。

和约瑟夫环问题类似，我们对新序列$arr'$进行重新赋值为$arr''=[1,2,3,...,i/2]$。

这样原问题是不是变成了规模一半的子问题了？

对于序列$arr''$的解应该是$f'(i/2)$（注意这里第一次是从右往左而不是从左往右，所以是$f'(\cdot)$）。

我们将$arr''$的值映射回$arr'$（乘以2即可映射回$arr'$），即可得到arr对应的问题的解。也就是说$f(i)=f'(i/2)*2$。

至此我们得到了下面两个递推公式：

$f(i)+f'(i)=i+1\\ f(i)=f'(i/2)*2$

稍作转换即可得到：$f(i)=2*(i/2+1-f(i/2))$。通过这个递推公式，我们可以很轻松的写出递归形式的代码：

1
2
3
4
5
6

class Solution {
    public int lastRemaining(int n) {
        if(n == 1) return n;
        return 2 * (n/2 + 1 - lastRemaining(n/2));
    }
}