390. Elimination Game

正规解法直接跳到代码上面一点的部分就可以了。但我想记录下自己的思考和尝试过程，希望二刷能看到问题所在。

找规律的时候写了好多，虽然规律很简单。

只要随便写3以上的例子，就应该发现，相邻的2个最后结果是一样的，n=8和n=9的结果都是6,n=10和n=11的结果都是8..

当时我的想法是，8 9消除2次之后就和4 5的消除情况一样，6 7和3 4一样，那既然需要用到前面的步骤，肯定是动态规划。

然而，不管是DP[I]来自DP[I-2]还是来自DP[I/2]都似乎不正确，我相信如果每一轮都是从左往右削减，那就简单多了，甚至不用动态规划。

重新入手，第一次是每2个删除1个；

第二次在第一次的基础上每2个删除1个，其实就是每4个删除1个；

第三次就是每8个删除一个。

这样以来最后一个幸存的就是不是2 4 8 16...的倍数的，假如每次都从左删除。

这里的问题是从右往左消减太可恶了。

会改变。

最后的结果就是分情况讨论，每删除一轮，都记录从哪个元素开始删除。

换句话说，都记录最左边的元素是哪一个，至于下一次删不删除它，也跟各种情况有关。

就2种情况，左还是右。

左的话第一个元素稳死，下一次的第一个变为当前的下一个。

当前的下一个的计算方式是当前+跳过的个数，第一次跳过2个，第二次跳过4个，第三次8个。。

从右的话，还跟目前剩下元素的奇偶性有关，偶数左边第一个会被保留；基数左边第一个又嗝屁了。

总之就2种情况，第2种情况里又有2种。。比一开始想的简单多了。。

public class Solution

{

    public int lastRemaining(int n)

    {

        if(n <= 1) return n;

        int res = 1;

        int left = n;               // how many elements left(not eliminated)

        int interval = 1;           // elimination interval

        boolean fromLeft = true;    // elimination process begins from left to right?

        while(left > 1)             // until only 1 element left

        {

            if(fromLeft)

            {

                res += interval;

            }

            else

            {

                if(left % 2 == 0)

                {

                    res = res;

                }

                else

                {

                    res += interval;

                }

            }

            left /= 2;

            interval*=2;

            fromLeft = !fromLeft;

        }

        return res;

    }

}

代码里逻辑性的东西我习惯尽量能不省就不省，这样结构更清晰。有些时候拼了命写在一行一大坨，可读性比较差，尤其是对于我这种智障来说。

巴特西

390. Elimination Game

最新文章

热门文章