算法每日一题——第七天——消除游戏

原题链接：力扣

分析:

输入一个n,我们就要对1到n的所有数就行消除。我在看见这道题最开始的想法是将1到n的所有数装到一个数组里面，被消除的数标记为-1，再进行下一次消除时遇见-1就跳过，但是这样写会非常麻烦。

我们先观察上面的样例：

第一次：1，2，3，4，5，6，7，8，9

第二次：2，4，6，8

第三次：2，6

第四次：6

可以发现每次的结果都是一个等差数列，第一次公差为1，第二次公差为2，第三次公差为4。公差的变化规律很容易发现(每次扩大两倍)。那我们就可以思考，是否可以用数列首项，尾项，公差来表示一组数呢？（后面用a1,an,d来分别表示首项，尾项和公差）

如果我们能找出首项和尾项的变化规律，那么我们就可以用他们来表示一组数了。

不难发现以下规律：

从左开始删：有偶数个整数时，a1 = a1 + d ; an = an(不变)

                     有奇数个整数时，a1 = a1 + d ; an = an - d

从右开始删：有偶数个整数时，a1 = a1(不变) ; an = an - d

                     有奇数个整数时，a1 = a1 + d ; an = an - d

找到以上规律，这道题就非常容易了。

接口代码：

int lastRemaining(int n)
{
    int a1 = 1;
    int an = n;
    int d = 1;
    while(1)
    {
        if(n == 1)
        return a1;
        if(n % 2 == 0)
        a1 += d;
        else
        {
            a1 += d;
            an -= d;
        }
        d *= 2;
        n /= 2;
        if(n == 1)
        return a1;
         if(n % 2 == 0)
         an -= d;
         else
        {
            a1 += d;
            an -= d;
        }
        d *= 2;
        n /= 2;
    }   
}