题解 | #牛牛扔牌#

思路：

题目的主要信息：

一个长度为n的字符串，用数字表示牌的点数，字母'C''D''H''S'表示花色，同一牌这两部分相连，即长度为n的字符串有 $n/2$ 张牌
如果还剩下素数张牌，则扔掉牌顶，如果还剩下非素数张牌则将牌底扔掉
求扔掉全部牌的顺序，输出字符串

方法一：暴力判断素数+字符串截取
具体做法：
对于每次剩下的牌数，我们可以暴力判断其是否是素数。我们用两个指针left和right指向牌顶和牌底的下标，每次剩下的n为素数我们就截取牌顶指针后两位字符，n为非素数我们就截取牌底指针后两位字符，直到n为0.
图片说明

class Solution {
public:
    bool isPrime(int a){
        if(a <= 1)
            return false;
        for(int i = 2; i * i <= a; i++) //循环判断是否是素数
            if(a % i == 0)
                return false;
        return true;
    }
    string Orderofpoker(string x) {
        int n = x.length() / 2; //字符串包括点数与花色
        string res = "";
        int left = 0; //牌顶
        int right = x.length() - 2; //牌底
        while(n){
            if(isPrime(n)){ //素数截取前面两个
                res += x.substr(left, 2);
                left += 2;
            }else{ //非素数截取后面两个
                res += x.substr(right, 2);
                right -= 2;
            }
            n--;
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n \sqrt n)$ ，其中 $n$ 并非字符串长度而是牌数即字符串长度的一半，判断每个数是否为素数每次为 $O(\sqrt n)$ ，外面一共 $n$ 次循环
空间复杂度： $O(1)$ ，res为返回必要空间，无额外空间

方法二：素数数组+双向队列
具体做法：
因为题目明确给出了 $1<=n<=10$ ，因此我们可以用一个数组直接存储这些数字是否是素数，然后利用数组直接判断。
同时，我们还可以用双向队列模拟这个过程，字符串所有字符入队列，素数弹出队列前端两个元素，非素数弹出队列后端两个元素。

class Solution {
public:
    string Orderofpoker(string x) {
        bool isPrime[11] = {false, false, true, true, false, true, false, true, false, false, false};
        deque<char> q;
        q.clear();
        for(int i = 0; i < x.length(); i++)  //进入双向队列
            q.push_back(x[i]);
        int n = x.length() / 2; //字符串包括点数与花色
        string res = "";
        while(!q.empty()){
            if(isPrime[n]){ //直接查看是否为素数
                res += q.front(); //添加两个队列前端的元素
                q.pop_front();
                res += q.front();
                q.pop_front();
            }else{
                char c1 = q.back(); //队列后端的元素要先加前面的再加后面的，因此先弹出的后加
                q.pop_back();
                char c2 = q.back();
                q.pop_back();
                res += c2;
                res += c1;
            }
            n--;
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，字符入队列为 $O(2n)$ ，后续只有一次循环的 $O(n)$
空间复杂度： $O(n)$ ，字符串的双向队列长度为 $2*n$ ，res属于必要空间