Leetcode 390.消除游戏

题目地址

思路

第一种方法肯定是遍历，暴力删除，但是数据量一大就容易超时。

第二种方法，我们想到利用等差数列来进行模拟。

我们定义首项a0,公差为d，项数为size。
其中公差每次都是翻倍，项数每次都是减半（向下取整）。
我们只需要更新首项，最后将其return就可以。

要怎么去更新首项呢？
首先我们知道：有从左到右删除和从右到左删除，两种方式。
所以我们先要判断是哪种方式。
如果是从左到右，就将a0+d；
如果是从右到左，判断此时的项数：如果项数是偶数，就保持a0不变。反则则a0+d。

基本思路如上，具体细节实现请看下面的代码，代码中也有部分注释，相信写的比较清楚。

代码实现（C++）

class Solution {
public:
    int lastRemaining(int n) 
    {
        int size=n;
        int a0=1;
        int d=1;
        int loop_time=0;  //定义删除轮数，初始为0轮，表示还未删除
        while(size!=1)
        {
            if(loop_time%2==0) //从左向右删除
            {
                a0=a0+d;
            }
            else if(loop_time%2==1)  //从右向左删除
            {
                if(size%2==0)
                {
                    a0=a0;
                }
                else if(size%2==1)
                {
                    a0=a0+d;
                }
            }
            size/=2;  //长度减半
            d*=2;  //公差加倍
            loop_time++;  //次数加1
        }
        return a0;
    }
};

总结

这道题是数学和编程模拟的结合，挺有趣的。