leetcode 390. Elimination Game 消除游戏 + 递归解决 + 寻找规律

绝地灬酷狼 2022-06-04 05:22 111阅读 0赞

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

下面是C++的做法，直接按照这个思路去做肯定超时，但是这也是最高效最简单的方法，我选择这么做，但是我相信应该存在类似数学公式的做法，网上看了一个答案十分简洁，

这个递归的做法实在是搞不懂，就这么办吧！

答案如下：

class Solution 
    {
    public:
        int lastRemaining(int n)
        {
            if (n == 1)
                return 1;
            if (n <= 4)
                return 2;
            if (n % 2 != 0)
                n -= 1;
            if (n % 4 != 0)
                return 4 * lastRemaining(n / 4);
            else
                return 4 * lastRemaining(n / 4) - 2;
        }
    };

但是我的做法是直接来做，代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        int lastRemaining(int n) 
        {
            vector<int> a(n,0);
            for (int i = 0; i < a.size(); i++)
                a[i] = i+1;
            int flag = true;
            while (a.size()>=2)
            {
                vector<int> tmp;
                if (flag)
                {
                    for (int i = 1; i < a.size(); i+=2)
                        tmp.push_back(a[i]);
                }
                else
                {
                    for (int i = a.size()-2; i >=0 ; i-=2)
                        tmp.push_back(a[i]);
                    reverse(tmp.begin(),tmp.end());
                }
                flag = !flag;
                a = tmp;
            }
            return a[0];
        }
    };