本文来自于对leetcode #### 390. 消除游戏的扩展与思考

last one to survive 最后一人存活问题

关于最后一人存活问题，可以抽象成：
给定一个数组，每次按照一定规则去除数组中的若干元素，直到剩下最后一个元素，返回这个元素

根据去除元素的规则的不同，可以衍生出不同的存活玩法。如果你是数组所有元素中的一个，你如何保证自己最后活下来呢？

下面将通过几个玩法，学习如何将实际问题抽象成数学问题，学习问题的抽象

玩法1：每次从左到右kill奇数位置上的人，直到剩下最后一个人

这个玩法下，每一轮都只有偶数位置上的人存活。如：

[1,2,3,4,5,6,7]
->[2,4,6]
->[4] return 4

上面的例子可以给出感性的认识，

• a.每一轮过后，剩下的元素个数 = 原元素个数 // 2
• b.剩下的元素个数的位置下标 = 原下标 / 2

活下来的人在之前的任何一轮中都处在偶数位置，那么由b可以知道，活下来的人的编号必然是2^N， 且2^(N+1) > 初始元素个数
例子中N=2

玩法2：先从左到右kill奇数位置上的人，然后从左到右kill偶数位置上的人，不断循环，直到剩下最后一个人

例如：

[1,2,3,4,5,6,7,8,9] // 左到右删奇数位
->[2,4,6,8] // 左到右删偶数位
->[2,6] // 左到右删奇数位
->[6] return 6

这种玩法下，由于删除规则在有规律的变化，因此不像玩法1那样直观

但我们可以将问题进一步抽象：

无论我们删除奇数位置还是删除偶数位置，剩下的 1/2 数组都必然是一个等差数列，只是首项和公差在不断变化。而我们要求的，就是长度为1的等差数列的首项

在数学上，对于等差数列，确定了首项和公差，就确定了一切；换句话说，确定了首项和第二项，就确定了一切

在这个问题中，删除导致的首项和公差的变化是有迹可循的，是跟随每轮的删除变化的：

• 左到右删奇数位，删除前的次项变成新首项，公差翻倍
• 左到右删偶数位，首项不变，公差翻倍

于是，我们顺理成章地写出代码：

class Solution:
    def lastRemaining(self, n: int) -> int:
        # 每次总要删除一半或者一半+1的数，即总会剩下n//2个数
        # 当前长度psuedo_len
        psuedo_len = n
        # 当前所在的删除轮数
        round = 0
        # 首项
        first = 1
        # 次项
        second  = 2
        # 公差
        delta = 1
        while psuedo_len != 1:
            round += 1
            # 奇数轮删除(从左向右删奇数位，原次项变成删除后的首项)
            if round % 2 == 1:
                first = second
            # 偶数轮删除（左到右删偶数位，首项不变）
            else:
                  pass
            # 公差翻倍
            delta = 2*delta
            second = first + delta
            psuedo_len = psuedo_len // 2
        return first

玩法3：先从左到右kill奇数位置上的人，然后从右到左反向kill奇数位置上的人，不断循环，直到剩下最后一个人

例如：

[1,2,3,4,5,6,7,8,9,10] // 左到右删奇数位
->[2,4,6,8,10] // 反向删奇数位
->[4, 8] // 左到右删奇数位
->[8] return 8

还是抽象化问题，抓住本质——每次删除元素后得到新的等差数列，确定首项和公差就可以确定一切

• 奇数轮删除，从左向右删奇数位，那么第二个数变成删除后的第一个数。公差翻倍
• 偶数轮删除，反向删除奇数位，如果删除前元素总个数是偶数，那么首项不变，否则原次项变成新首项。公差翻倍

class Solution:
    def lastRemaining(self, n: int) -> int:
        # 每次总要删除一半或者一半+1的数，即总会剩下n//2个数
        psuedo_len = n
        round = 0
        first = 1
        second = 2
        delta  = 1
        while psuedo_len != 1:
            round += 1
            # 奇数轮删除(从左向后，第二个数变成删除后的第一个数)
            if round % 2 == 1:
                first = second
            # 偶数轮删除（从右向左删）
            else:
                if psuedo_len % 2 == 0:
                    # 删除后的第一个数不变
                    pass
                else:
                    # 第二个数变成删除后的第一个数
                    first = second     
            delta = 2*delta
            second = first + delta
            psuedo_len = psuedo_len // 2
        return first

---

现在回过头来，我们可以给玩法1也做类似的解答

class Solution:
    def lastRemaining(self, n: int) -> int:
        psuedo_len = n
        round = 0
        first = 1
        second = 2
        delta  = 1
        while psuedo_len != 1:
            round += 1
            first = second
            delta = 2*delta
            second = first + delta
            psuedo_len = psuedo_len // 2
        return first