leetcode:消除游戏（等差数列方法）

思路：
暴力模拟超时了
听说可以用数学找规律，但答案不大看得懂555
还是用等差数列方法吧。。。

代码：

class Solution:
    def lastRemaining(self, n: int) -> int:
        # 用等差数列模拟
        # 不用引入list
        # 保留一头一尾
        a1, an = 1, n
        k, cnt, step = 0, n, 1
        while cnt > 1:
            # 正向
            if k % 2 == 0:
                a1 += step
                if cnt % 2:
                    an -= step
            # 反向
            else:
                if cnt % 2:
                    a1 += step
                an -= step
            k += 1
            cnt //= 2
            step *= 2
        return a1

总结：
不用list，只保留一头一尾，余下的元素个数，和当前的步长，根据奇偶层和奇偶个数更新一头一尾
好理解！
复杂度log n