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

0x00 题目介绍

简单介绍一下题目意思

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

Example:

1
2
3
4
5
6
7
8
9
Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

Output:
6

0x01 解法

解法一 按部就班

  1. 思想：直接按照题目意思，模拟删除步骤
  2. 代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    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);
    代码思想简单，易懂，一般最开始想到的也是这种算法

解法二 来去递归(一)

  1. 思想

    模拟去回删除元素,去即为从左到右,回即为从右往左,用一个变量代表状态,
    每轮删除后剩余这轮元素的一半.递归退出条件为当剩余元素为

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

    1). 从左往右删除

    那么每次删除掉的元素为奇数项元素,剩下的元素里全部都是偶数元素,并且最终结果也在这些元素里面.那么此时我们将所有元素同时除以2,此时元素又变为{1N/2},此时问题就变为找出{1N/2}剩余元素2即:F(N) = 2F(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 或者在开始的基础上加一

2.递归版本代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
n:元素个数
direction:删除方向 true:从左往右 false:从右往左
*/
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);
}

int lastRemaining(int n) {
       return getNext(n,true);
}

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

3.迭代版本代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
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(logN)

解法三 来去递归(二)

  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为奇数的时候也是一样,读者可以手动模拟一下

  2. 代码

    1
    2
    3
    4
    5
    6
    7
    int lastRemaining(int n) {
            if(n <= 1) { return 1; }
            //每次需要删除元素减半
            n >>= 1;
            //将方向反转  且结果需要乘以2
            return (1 + n - lastRemaining2(n)) << 1;
        };

    时间复杂度O(logN) 空间复杂度O(1)
    短短三行代码就解决了问题,短小精悍!

0x02结论

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