Elimination Game

这道题目出于leetcode,题目虽然很简单但是很有趣，因为有趣才能称得上游戏吧！

0x00 题目介绍

简单介绍一下题目意思

给定一个数字N（N>0），一个列表存着1～N的数字。每次从左到右从第一个数字开始，然后隔开一个数字删除数字，一直删除到最后再从右向左删除，一直删除到只剩下一个数字。

Example:

Input:

n = 9,

1 2 3 4 5 6 7 8 9

2 4 6 8

2 6

6

Output:

6

0x01 解法

解法一按部就班

思想：直接按照题目意思，模拟删除步骤
代码：

int lastRemaining(int n) {

        int start = 1, step = 1;

        while (n > 1) {

            //模拟删除元素一直到最后元素

            start += step + (n-2)/2 * 2*step;

            //每删除一轮剩余元素为该轮元素的一半

            n /= 2;

            //每次到达最后一个元素反向并且步数扩大两倍

            //因为每次都隔开删除一个元素，

            //所以下一轮的步数都是上一次的两倍

            step *= -2;

        }

        return start;

}

算法时间复杂度:O(logN),空间复杂度O(1);

代码思想简单，易懂，一般最开始想到的也是这种算法

解法二来去递归(一)

思想

模拟去回删除元素,去即为从左到右,回即为从右往左,用一个变量代表状态,

每轮删除后剩余这轮元素的一半.递归退出条件为当剩余元素为

我们设F(N) 为从{1~N}删除的剩余元素.

1). 从左往右删除

那么每次删除掉的元素为奇数项元素,剩下的元素里全部都是偶数元素,并且最终结果也在这些元素里面.

那么此时我们将所有元素同时除以2,此时元素又变为{1_{N/2},此时问题就变为找出{1}N/2}剩余元素*2

即:F(N) = 2*F(N/2);

(方向----> N为偶数8) 1 2 3 4 5 6 7 8

剩余的元素在2{1,2,3,4}里面即2F(8/2);

(方向----> N为奇数9)

1 2 3 4 5 6 7 8 9

剩余元素为2{1,2,3,4}即 2F(9/2)

2). 从右往左删除

如果最后一个元素是偶数,如果我们从右往左删除,剩余元素全部为奇数,为了使得剩余元素全部为偶数

(方便下一步运算,因为我们需要把N的问题分解为N/2的问题)那么我们将所有元素加1,这样删除后

剩余元素就全部变为偶数了,为了弥补加1,我们需要在获得的结果后减1;

所以当从左往右的时候F(N) = F(N/2)-(1-N%2)=F(N/2)-1+N%2

比如:当N=8 list = {1,2,3,4,5,6,7,8}

(方向<---- N为偶数8)

1 2 3 4 5 6 7 8

答案在剩余元素{1,3,5,7}里面,如果我们写作2{1,2,3,4}答案明显不对,需要修正变为2{1,2,3,4}-1即2*F(8/2)-1;

(方向<---- N为奇数9)

1 2 3 4 5 6 7 8 9

剩余元素为2{1,2,3,4}即 2F(9/2)

如果我们使用2*F(4/2) 答案明显不对了,所以我们需要在此基础上需要加上一个offset 1 或者在开始的基础上加一
递归版本代码

int getNext(int n,bool direction){

    if(n==1) return 1;

    //判断方向 从左往右

    if(direction) return 2*getNext(n/2,!direction);

    // 从右往左  偶数需要减一

    else return 2*(getNext(n/2,!direction))-1+n%2;

}

int lastRemaining1(int n) {

       return getNext(n,true);

}

时间复杂度O(logN) 空间复杂度O(logN)

迭代版本代码

/*

direction:删除方向 true:从左往右 false:从右往左

ratio: 记录当前删除深度

offset: 偏移值(分析如上)

*/

int lastRemaining(int n) {

    bool direction = true;

    int ratio = 1;

    int offset = 0;

    while(n!=1){

        if(!direction && n%2==0)

            offset+=ratio;

        ratio<<=1;

        n/=2;

        direction=!direction;

    }

    return ratio-offset;

}

时间复杂度O(logN) 空间复杂度O(1)

解法三来去递归(二)

算法思想

也是来往依次删除,把每次删除操作统一为一个方向.这样不需要每次判定方向如何,

也不需要判定是否为偶数再去减掉偏移值.

如何将删除方向统一为一个方向呢?

注意:我们每次都是先从左往右删除

例如:当N=8时

方向(---->) 1 2 3 4 5 6 7 8

剩余元素在:2*{1,2,3,4}里面, 接着删除,此时我们删除方向反向为右往左.

如果我们将{1,2,3,4}反转,并用4+1-反转后的结果

即:4+1 - {1,2,3,4} = {4,3,2,1} 此时我们从右往左删除{4,3,2,1}就转化为从左往右删除{1,2,3,4}

方向就统一了起来.当然N为奇数的时候也是一样,读者可以手动模拟一下
代码

int lastRemaining(int n) {

        if(n <= 1) { return 1; }

        //每次需要删除元素减半

        n >>= 1;

        //将方向反转  且结果需要乘以2

        return (1 + n - lastRemaining2(n)) << 1;

    };

时间复杂度O(logN) 空间复杂度O(1)

短短三行代码就解决了问题,短小精悍!

0x02结论

有趣的题目千篇一律,精致的解法百里挑一!

巴特西

Elimination Game题解

Elimination Game

0x00 题目介绍

0x01 解法

解法一按部就班

解法二来去递归(一)

解法三来去递归(二)

0x02结论

最新文章

热门文章

巴特西

Elimination Game题解

Elimination Game

0x00 题目介绍

0x01 解法

解法一 按部就班

解法二 来去递归(一)

解法三 来去递归(二)

0x02结论

最新文章

热门文章

解法一按部就班

解法二来去递归(一)

解法三来去递归(二)