[LeetCode] Elimination Game 淘汰游戏

There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example:

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

这道题是LeetCode第二次编程比赛的题，然而博主并没有做出来，博主用的方法是那种最笨的方法，用一个数组把n个数组都存起来，然后根据循环的奇偶来决定是从左还是从右删除，结果不幸超时TLE了。后来通过想大神请教和上网搜索，发现这道题用递归来做很简单，我们用一个bool型变量left2right，为true表示从左往右，为false表示从右往左遍历。当n为1时，不论从左往右还是从右往左都返回1。如果n大于1，且是从左往右的话，我们返回2倍的对n/2的从右往左的遍历；如果是从右往左的话，稍稍麻烦一些，我们肯定还是要对n/2调用递归函数的，但是要分奇偶情况，如果n为奇数，返回2倍的对n/2的从左往右的遍历的值；如果n为偶数，2倍的对n/2的从左往右的遍历的值，再减去1。具体这样的原因，楼主还在研究中，也不是太清楚：

解法一：

class Solution {
public:
    int lastRemaining(int n) {
        return help(n, true);    
    }
    int help(int n, bool left2right) {
        if (n == 1) return 1;
        if (left2right) {
            return 2 * help(n / 2, false);
        } else {
            return 2 * help(n / 2, true) - 1 + n % 2;
        }
    }
};

下面这种方法相当的叼，一行就搞定了简直丧心病狂啊。第一次从左往右删除的时候，奇数都被删掉了，剩下的都是偶数。如果我们对所有数都除以2，那么得到一个1到n/2的新数列。下一次我们从右往左删出，那么返回的结果应该是调用递归的结果lastRemaining(n / 2)在数组1到n/2之间的镜像。何为镜像，比如1, 2, 3, 4这个数字，2的镜像就是3, 1的镜像是4，参见代码如下：

解法二：

class Solution {
public:
    int lastRemaining(int n) {
        return n == 1 ? 1 : 2 * (1 + n / 2 - lastRemaining(n / 2));    
    }
};

下面这种迭代的解法是我请教另一位大神的方法，个人感觉也非常叼，膜拜大神中。我们先来看两个简单的例子：

n = 8
1 2 3 4 5 6 7 8
   2    4    6   8
   2          6
               6
n = 7      
1 2 3 4 5 6 7
   2    4    6
         4

如果我们仔细观察，我们可以发现从左往右删的时候，每次都是删掉第一个数字，而从右往左删的时候，则有可能删掉第一个或者第二个数字，而且每删一次，数字之间的距离会变为之前的两倍。我们要做的是每次记录当前数组的第一个数字，而且我们再通过观察可以看出，从右往左删时，如果剩下的数字个数是偶数个时，删掉的是第二个数字；如果是奇数个的时候，删掉的是第一个数字。总结出了上述规律，就可以写出代码如下：

解法三：

class Solution {
public:
    int lastRemaining(int n) {
        int base = 1, res = 1;
        while (base * 2 <= n) {
            res += base;
            base *= 2;
            if (base * 2 > n) break;
            if ((n / base) % 2 == 1) res += base;
            base *= 2;
        }
        return res;
    }
};

本文转自博客园Grandyang的博客，原文链接：淘汰游戏[LeetCode] Elimination Game ，如需转载请自行联系原博主。