390. 消除游戏

分析

当数字从下一轮还原映射到上一轮时，其行为有两个决定：

1. 映射的轮数是奇数还是偶数
2. 映射的时候数组长度是原来的两倍，还是两倍+1。

如何理解这一点？先以n=9为例子，从上到下分别经过了几轮筛选：

1. arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
2. arr = [2, 4, 6, 8]
3. arr = [2, 6]
4. arr = [6]

我们仿照约瑟夫环的思路，尝试还原存活节点在原数组中的编号。当只剩下一个存活节点时，其编号为1。

1. 在第4轮中存活的节点为1号，它在第3轮中是2号。映射关系为$n_{i+1}=2n_i$
2. 在第3轮中存活的节点为2号，它在第2轮中是3号，映射关系为$n_{i+1}=2n_i+1$
3. 在第2轮中存活的节点为3号，它在第1轮中是6号，映射关系为$n_{i+1}=2n_i$

由现象可猜测，当存活节点从下一轮的编号还原回上一轮时，其映射关系要么为$n_{i+1}=2n_i$，要么为$n_{i+1}=2n_i+1$。那么如何确定是哪一种呢？

• 当数组倒数第i+1轮的长度为奇数时，映射关系一定是$n_{i+1}=2n_i$。举个例子当从第1轮映射到第2轮时，无论从左边还是从右边删除，删除的节点都为[1,3,5,7,9]，显然留下的都是[2,4,6,8]，而他们组成后面的1到4号。
• 当长度为偶数时，假设倒数第i+1轮为arr = [1,2,3,4]，则
  • 如果是在奇数轮，要从左往右删除，那删除[1,3]，留下[2,4]，后者会变成倒数第i轮的编号1和2，所以映射关系为$n_{i+1}=2n_i$
  • 如果是在偶数轮，要从右往左删除，那么留下的是1,3，映射关系为$n_{i+1}=2n_i+1$

那么如何确定当轮数组的长度是奇数还是偶数？假如n=9，首轮的轮号是0。

• 第0轮时，其长度为$(1001{)}_2$，是奇数，最低位是原来的第0位。
• 第1轮时，长度为$(100{)}_2$，是偶数，最低位是原来的第1位。
• 第2轮时，长度为$(10{)}_2$，是偶数，最低位是原来的第2位。

观察可知，第i轮数组长度是奇数或偶数，取决于其第i位上为1或者0。

综上，就可以递推出每一轮里存活节点的编号了。

答案

class Solution:
    def lastRemaining(self, n: int) -> int:
        i = 32
        while i >= 0 and (((1 << i) & n) == 0):
            i -= 1
        
        # 最高位为2<
        d = i
        alive = 1
        cnt = 0
        while i >= 0:
            is_one = ((1 << i) & n) != 0
            if is_one:
                if cnt > 0:
                    alive *= 2
            else:
                if (d % 2) == (cnt % 2):
                    alive *= 2
                else:
                    alive = 2 * alive - 1
            cnt += 1
            i -= 1
        
        return alive
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

总结

看起来讨论区用了别的做法，有用等差数列的官方题解，有用递归的【宫水三叶】约瑟夫环运用题。但本文思路是自己想的，所以就这么记着吧。