题解 | #牛牛扔牌#

题意整理

给定n张扑克牌，每张牌由字符1-9，以及对应的花色字符组成。
如果还剩非素数张牌，则扔掉牌低的牌；还剩素数张牌，则扔掉牌顶的牌。
返回扔牌顺序的字符串。

方法一（字符串截取）

1.解题思路

新建可变字符串sb。
如果剩余牌数不是素数，从尾部截取对应的牌放入sb，保留截取后的字符串。
如果剩余牌数是素数，从头部截取对应的牌放入sb，保留截取后的字符串。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param x string字符串 字符串从前到后分别是从上到下排列的n张扑克牌
     * @return string字符串
     */
    public String Orderofpoker (String x) {
        int n=x.length()/2;
        //新建可变字符串
        StringBuilder sb=new StringBuilder();
        while(n>0){
            //如果不是素数，从尾部截取对应的牌放入sb
            if(!isPrime(n)){
                sb.append(x.substring(2*n-2));
                //x保留截取之后的部分
                x=x.substring(0,2*n-2);
            }
            //如果是素数，从头部截取对应的牌放入sb
            else{
                sb.append(x.substring(0,2));
                //x保留截取之后的部分
                x=x.substring(2);
            }
            n--;
        }
        return sb.toString();
    }

    //判断是否是素数
    private boolean isPrime(int x){
        return x==2||x==3||x==5||x==7;
    }
}

3.复杂度分析

时间复杂度：由于n限定在1到10之间，判断素数的时间复杂度为常数级别，每一次截取的时间复杂度是 $O(n)$ ，需要截取n次，所以时间复杂度是 $O(n^2)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度是 $O(1)$ 。

方法二（队列模拟）

1.解题思路

初始化队列和可变字符串sb。
如果是素数，取队列头部两字符，放入sb。
如果不是素数，取队列尾部两字符，交换顺序后放入sb。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 
     * @param x string字符串 字符串从前到后分别是从上到下排列的n张扑克牌
     * @return string字符串
     */
    public String Orderofpoker (String x) {
        int n=x.length()/2;
        //初始化队列
        LinkedList<Character> queue=new LinkedList<>();
        for(char c:x.toCharArray()){
            queue.offer(c);
        }
        //初始化可变字符串
        StringBuilder sb=new StringBuilder();
        while(n>0){
            //如果是素数，取队列头部两字符，放入sb
            if(isPrime(n)){
                char c=queue.pollFirst();
                char d=queue.pollFirst();
                sb.append(c).append(d);
            }
            //如果不是素数，取队列尾部两字符，交换顺序后放入sb
            else{
                char c=queue.pollLast();
                char d=queue.pollLast();
                sb.append(d).append(c);
            }
            n--;
        }
        return sb.toString();
    }

    //判断是否是素数
    private boolean isPrime(int x){
        if(x==1) return false;
        for(int i=2;i*i<=x;i++){
            if(x%i==0){
                return false;
            }
        }
        return true;
    }
}

3.复杂度分析

时间复杂度：起初全部元素入队的时间复杂度是 $O(n)$ ，每次判断是否是素数后，弹出的时间复杂度是 $O(1)$ ，需要判断n次，所以最终的时间复杂度是 $O(n)$ 。
空间复杂度：需要额外长度为 $2*n$ 队列，所以空间复杂度是 $O(n)$ 。