390. 消除游戏（python)

题目:
给定一个从1 到 n 排序的整数列表。
首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。
第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。
我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
返回长度为 n 的列表中，最后剩下的数字。

示例：

输入:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

输出:
6

思路:
每删一次，数字之间的距离会变为之前的两倍，并且：

从左往右删的时候，每次都是删掉第一个数字；
从右往左删的时候，则有可能删掉第一个或者第二个数字；
如果剩下的数字个数是偶数，删掉的是第二个数字；
如果剩下的数字个数是奇数，删掉的是第一个数字；
所以我们只需要计算出并记录当前数组的第一个数字，只要第一个数字有了，后面的数字都可以计算出来了。

代码

class Solution:
    def lastRemaining(self, n: int) -> int:
        base=1
        res=1
        while(base*2<=n):
            res+=base
            base*=2
            if(base*2>n):
                break
            if(int((n/base))%2==1):
                res+=base
            base*=2
        return res