LC390.消除游戏

Created: January 2, 2022 1:46 PM

声明：我写的文章只是为了只有一个目的———把方法讲清楚、讲通透。 OJ上很少存在某个人原创的方法，大部分只是对已有的方法的重复。

⚠️长度警告

Brute Force 暴力法

我们先来分析数组手动模拟的不可行性。

注意到 $1 \le n \le 10^9$。假设每个数 16bit，存放所有中间数需要最多 $16 \times 10^9$bit 也就是约 2GB！！。
就算预处理第一轮去除所有奇数，也要1GB。
要知道一般的OJ平台的上限仅仅是MB级别。因此，显然不可行。

我们必须寻求一些数学方法，一个是从数列的角度，一个是从函数的角度。

数列的角度

从题目的描述来看，我们的输入，无论怎么消除，仅仅只是一串等差数列。

回顾等差数列的三要素：1. 首项 $a_1$； 2. 公差 $d$； 3. 项数 $n$；

并有如下公式成立：

$$a_n = a_1 + (n-1)\cdot d$$

因此，就没有必要再存储数列中的每个元素的值了。

如果把输入看作是一个等差数列 $a^0$。e.g. 1, 2, 3, 4 ,5

那么，消除第一轮的产生一个新的等差数列 $a^1$。e.g. 2, 4

那么，消除第二轮的产生一个新的等差数列 $a^2$。e.g. 2

以此类推，消除$turn$轮产生一个新的等差数列 $a^{turn}$。

不难看出，每一轮消除过后存在一下差别：

公差 $d$ 加倍了
首项 $a_1$ 变了
项数 $n$ 变了

于是我们就要探索一下这三者是怎么变的：

对于公差 $d$，无论是从左向右还从右向左消除，都会加倍
对于项数 $n$，与公差类似，每次都会减半，准确的说，是$\left \lfloor \frac{n}{2}\right \rfloor$ 。
首项$a_1$则相对复杂，需要讨论一下消除轮数 $turn$ 与项数$n$的奇偶性。
注：最好自己拿草稿纸推敲一下
首先讨论轮数 $turn$，再讨论项数$n$，由于规定起始 $turn = 0$
- 当 $turn$为偶数时，从左向右消除
  - 此时一定有$a_1^{turn} = a_1^{turn-1}+d$
- 当 $turn$为奇数时，从右向左消除
  - 当且仅当$n$为奇数时，有$a_1^{turn} = a_1^{turn-1}+d$

经过以上讨论，只要把以上的变化翻译成代码，反复迭代，直到$n=1$即可。

class Solution {
public:
    int lastRemaining(int n) {
        int turn = 0;
        int step = 1;
        int cnt = n;
        int a_1 = 1;
        
        
        while(cnt > 1) {
            if(turn % 2 == 0) { // turn 是偶数 从左向右
                a_1 = a_1 + step;
            } else { // 从右向左
                if(cnt & 1 == 1) a_1 = a_1 + step;
            }
            step = step << 1;
            cnt = cnt >> 1;
            turn++;
        }      
        return a_1;
    }
};

（重点）函数的角度

在做解微分方程的时候，我们希望解出某个函数的解析解（上面的方法就是一个）。

但是有时候当我们无法得到解析解时，也可以考虑将方程简化，得到一个函数的递推关系。

定义：$f(n)$是以自左向右开始，间隔一个消除直到只剩一个的元素的函数。

注：说白了就是题目要求我们写的代码。

定义：$g(n)$是以自右向做开始，间隔一个消除直到只剩一个的元素的函数。

以上的两个函数存在以下性质：

$$f(n)+g(n)= n+1$$

【证明】

C 1 line solution with explanation - LeetCode Discuss

令输入序列为 $I$，输入序列$I$的逆序列记作 $I_{reverse}$

令 $r=f(n)$,

由于，$**g(i)$等价于将 $f(i)$的输入序列$I$ 的逆序 $I_{reverse}$ ，**经由$f(i)$输出得到$r_{reverse}$

我们记作

$$g(n) = f_{reverse}(n)$$

注意到 $\forall x \in I, x_{reverse} \in I_{reverse}, x_{reverse}=n+1-x$

于是 $r + r_{reverse} = f(n)+g(n) = n+1-x+x=n+1$

$Q.E.D.$

并且，由题意可知，有以下方程组成立：

$$ f(n) = 2\cdot g(\left \lfloor \frac{n}{2} \right \rfloor)\ $$

$$ g(n) = 2\cdot f(\left \lfloor \frac{n}{2} \right \rfloor)\ $$

$$ f(1) = g(1) = 1 $$

综上，有 $$ f(n) + g(n) = n+1\ $$

$$ \Rightarrow f(\left\lfloor\frac{n}{2}\right\rfloor)+g(\left\lfloor\frac{n}{2}\right \rfloor)= \left\lfloor\frac{n}{2}\right \rfloor + 1 $$

由于 $$ f(n)=2\cdot g(\left\lfloor\frac{n}{2}\right \rfloor) $$ 于是得到递归式： $$ f(\left\lfloor\frac{n}{2}\right \rfloor) + \frac{1}{2} f(n) = \left\lfloor\frac{n}{2}\right \rfloor + 1 \ $$ 即

$$ f(n) =2\cdot [ \left \lfloor \frac{n}{2} \right \rfloor + 1 -f(\left \lfloor \frac{n}{2} \right \rfloor) ](*) $$

由$(*)$可以得到递归代码：

int lastRemaining(int n) {
    return n == 1 ? 1 : 2 * (1 + n / 2 - lastRemaining(n / 2));
}

LC390.消除游戏#

Brute Force 暴力法#

数列的角度#

（重点）函数的角度#

LC390.消除游戏

Brute Force 暴力法

数列的角度

（重点）函数的角度