题解 | #牛牛扔牌#

牛牛扔牌

http://www.nowcoder.com/practice/e2cb4ea9888040ebb24eeed547a8d63a

牛牛扔牌

描述

现在有n张扑克牌，每张扑克牌都有点数和花色两部分组成。点数为‘1’-‘9’的正整数，花色为'C','D','H','S''其中的一个，分别表示梅花、方块、红桃、黑桃。现在想按一定的顺序把这n张牌扔掉。扔牌顺序的规则如下1.：
1.如果现在还剩素数张牌，则将牌顶的牌扔掉
2.如果现在还剩非素数张牌，则将牌底的牌扔掉
求扔牌顺序是什么，请返回扔牌顺序的字符串

示例1

输入："3C8D6H3D"

返回值："3D3C8D6H"

说明：开始n=4，为非素数，扔掉牌底的牌3D
n=3，为素数，扔掉牌顶的牌3C
n=2，为素数，扔掉牌顶的牌8D
n=1，为非素数，扔掉牌底的牌6H

示例2

输入："8S8S8S8S8S8S8S"

返回值："8S8S8S8S8S8S8S"

说明：因为全是8S，所以扔牌顺序的每一张牌也都是8S

方法一

思路分析

本题的思路其实比较简单，循环遍历整个字符串（由于一张牌由两个字符构成，因此只需要遍历字符串长度的一半即可），然后判断当前长度是否为素数，如果是素数，那么将字符串开始位置的两个字符赋值给字符串temp，开始位置index向后增加两个位置；如果是非素数，那么将字符串末尾位置的两个字符赋值给字符串temp，末尾位置index向前增加两个位置；直到遍历完即可。

图解

核心代码

class Solution {
public:
    /**
     * 
     * @param x string字符串 字符串从前到后分别是从上到下排列的n张扑克牌
     * @return string字符串
     */
    string Orderofpoker(string x) {
        // write code here
        int length_x =x.length();
        int current_len=length_x/2;
        string temp="";
        int left=0;
        int right=length_x-1;
        for(int i=0;i<length_x/2;i++)//循环次数减半
        {
            if(prime(current_len))
            {
                temp+=x[left];
                temp+=x[left+1];
                left+=2;//开始位置向后两个位置
                
            }
            else
            {
                temp+=x[right-1];
                temp+=x[right];
                right-=2;//末尾位置向前两个位置
            }
            current_len--;
        }
        return temp;
    }
    
    int prime(int n)//判断是否为素数
    {
      if (n==0||n==1) 
      {
        return 0;
      }
    for(int i=2;i*i<=n;i++)//只需要判断到平方根n即可
    {
        if (n%i == 0) 
        {
            return 0;
        }
    }
    return 1;
    }
};

复杂度分析

时间复杂度：代码时间开销主要在遍历字符串，以及判断素数，设$n$表示字符串长度，循环遍历次数为$n/2$，需要对$n/2$个数判断是否为素数，时间复杂度为 $O(\sqrt{n})$ ，因此总的时间复杂度为 $O(n\sqrt{n})$
空间复杂度：额外的空间复杂度为$O(1)$

方法二

思路分析

本题中给出了n的取值范围，因此可以预先给出n之内的整数的素数判断，然后在进行判定时直接进行查询，可以降低时间复杂度。

核心代码

class Solution {
public:
    /**
     * 
     * @param x string字符串 字符串从前到后分别是从上到下排列的n张扑克牌
     * @return string字符串
     */
    string Orderofpoker(string x) {
        // write code here
        int length_x =x.length();
        if(length_x<0||length_x%2!=0) return "";
        int current_len=length_x/2;
        string temp="";
        int left=0;
        int right=length_x-1;
        int array[11]={0,0,1,1,0,1,0,1,0,0,0};
        for(int i=0;i<length_x/2;i++)//循环次数减半
        {
            if(array[current_len])
            {
                temp+=x[left];
                temp+=x[left+1];
                left+=2;//开始位置向后两个位置
                
            }
            else
            {
                temp+=x[right-1];
                temp+=x[right];
                right-=2;//末尾位置向前两个位置
            }
            current_len--;
        }
        return temp;
    }
};

复杂度分析