Leetcode.390 Elimination Game

390. Elimination Game

思路

给定$1,2,...,n$，然后按照题目的规则不断删除一些数，求最后剩下的数。

思路一

我首先想到的就是按照题目的规则进行模拟，但不要纯暴力模拟，那样肯定超时，还是要根据其中一些规律。 有一个很容易发现的规律：每次剩下的数都是一个等差数列，而且等差分别为$1, 2, 4...$。 为此我们可以用一个循环，每次记录剩下的数的第一个数start和最后一个数$end$以及等差$diff$，不断循环直到 $start = end$ 。

思路二

一个代码很简洁的递归解法：

我们设 * ML(n)代表第一次是从左往后的情况下最终剩下的数，这就是要我们写的函数； * MR(n)代表第一次是从右往左的情况下最终剩下的数；

注意我们第一次将所有奇数都删除了，将剩下所有偶数都除2就得到序列$1,2,...,\frac n 2$。即我们有ML(n) = 2 * MR(n/2)。 又因为我们有ML(n) + MR(n) = n + 1（证明见讨论区）， 所以ML(n) = 2 * (n/2 + 1 - ML(n/2))。根据这个公式我们就可以写出递归函数了，就一行。

C++

思路一

class Solution {
public:
    int lastRemaining(int n) {
        int start = 1, end = n, diff = 1;
        int i = 0; // i记录循环的次数
        while(start != end){
            if(!(i & 1)){ // 从前往后, start可直接写出
                start += diff; 
                diff <<= 1;
                end = (end - start) / diff * diff + start;
            }
            else{ // 从后往前, end可直接写出
                end -= diff;
                diff <<= 1;
                start = end - (end - start) / diff * diff;
            }
            
            i++;
        }
        return start;
    }
};

思路二

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