leetcode每日一题 390.消除游戏

• 题目链接：

390.消除游戏

• 题解：

考虑记录三个状态 ，就可以确定整个列表arr，

我们分别记录列表左端点l,右端点r,以及步长len，

初始时状态有l = 1,r = n,len = 1;

考虑从左向右删除时，会转移到l1 = l + len,r1 = r : r - len ? (r - l)%(2 * len) != 0,len1 = 2 * len

从右向左类似

通过这样不断转移最后到达l >= r的时候返回r即可

• 代码：

int lastRemaining(int n)
{
    int l = 1, r = n, len = 1;
    int o = 0;
    while(l < r)
    {
        if(o == 0)
        {
            if((r - l) % (2 * len) == 0) r = r - len;
            l = l + len;
        }
        else
        {
            if((r - l) % (2 * len)== 0) l = l + len;
            r = r - len;
        }
        len = len * 2;
        printf("%d %d %d\n",l,r,len);
        o ^= 1;
    }
    return r;
}