Elimination Game

题目来源
淘汰游戏，先从前往后淘汰，再从后往前淘汰，每次都是每隔一个淘汰一个，问最后剩下什么数字。
我是记录了开始和结尾，不断改变更新，直到开始和结尾是一样的。
复杂度是O(logn)。

class Solution {
public:
    int lastRemaining(int n) {
        int curStart = 1, curEnd = n, interval = 1;
        while (curStart != curEnd) {
            int tmp = curStart;
            if (((abs(curEnd - curStart)) / interval + 1) % 2 == 0) {
                curStart = curEnd;
                curEnd = tmp + interval;
            }
            else {
                curStart = curEnd - interval;
                curEnd = tmp + interval;
            }
            interval *= -2;
        }
        return curStart;
    }
};

看了下讨论区，解法更加简洁明了。只记录最小的数字、间隔、剩余数字个数以及是否从左边开始。靠这些就可以对这些记录进行更新。直到剩余数字个数为1。

class Solution {
public:
    int lastRemaining(int n) {
        int curHead = 1, interval = 1, remaining = n;
        bool isLeft = true;
        while (remaining > 1) {
            if (isLeft || remaining % 2 == 1)
                curHead += interval;
            remaining /= 2;
            interval *= 2;
            isLeft = !isLeft;
        }
        return curHead;
    }
};