PAT乙级1003

题目链接

https://pintia.cn/problem-sets/994805260223102976/problems/994805323154440192

题解1

这个是我自己的方法，..…刚开始做题，还啥都不会啊。

只能过4个Case，Case5过不了，得19分，还不知道哪里错了（让强迫症很难受啊）。

第1个条件很简单，判断无非法字符即可。

第2个条件，是xPATx，易得：当字符串中有PAT时，PAT左右两边字符串应相等。

第3个条件，它依赖于前两个条件，特别是第2个，所以可以采取递归的形式。

代码如下：

import java.util.Scanner;

/**
 * PTABasicLevel 1003
 * https://pintia.cn/problem-sets/994805260223102976/problems/994805323154440192
 */
public class Main {
    public static void main(String[] args) {
        // 打开scanner
        Scanner scanner=new Scanner(System.in);

        // 用户输入的字符串
        String str=null;

        // 获取测试组数
        int T=scanner.nextInt();


        // T组测试
        while( T-- > 1){

            // 获取用户输入的字符串
            str=scanner.next();

            // 输出结果
            System.out.println(isValid(str)?"YES":"NO");
        }

        // 获取用户输入的字符串
        str=scanner.next();

        // 输出结果
        System.out.print(isValid(str)?"YES":"NO");

        // 关闭scanner
        scanner.close();
    }

    /**
     * 判断一个字符串是否有效
     * @param str 一个字符串
     * @return 结果
     */
    public static boolean isValid(String str){

        // 字符串长度
        int strLength=str.length();

        // 字符串中P和T首次出现的位置
        int indexOfP=-1;
        int indexOfT=-1;

        // 字符串中P和T的数量
        int numOfP=0;
        int numOfT=0;

        // 字符串应仅由P、A、T组成，且P和T各有一个，判断过程中记录P和T的位置和个数
        for(int i=0;i<strLength;i++){
            // 存在PAT以外的字母，字符串就是错误的
            if(str.charAt(i)=='P'){
                indexOfP=i;
                numOfP++;
            }else if(str.charAt(i)=='T'){
                indexOfT=i;
                numOfT++;
            }else if(str.charAt(i)!='A'){
                return false;
            }
        }

        // P或T不是1个，或者是P和T的位置有问题（应该是PxT，x是正整数个A拼成的字符串）
        if(numOfP!=1||numOfT!=1||indexOfT-indexOfP<2){
            return false;
        }

        // 在这一行已可以确定字符串只由1个P和一个T和一些A组成，且P和T位置正确

        // 条件2
        // P和T中间只有1个A
        if(indexOfT-indexOfP==2){
            String x=str.substring(0,indexOfP);
            // PAT左右是相等的x
            if(indexOfT+1==str.lastIndexOf(x)){
                return true;
            }
            // PAT左右不相等
            else{
                return false;
            }
        }
        // 条件3
        else{
            String a=str.substring(0,indexOfP);
            int indexOfRightA=str.lastIndexOf(a);

            // 剥掉Pb和T中间的A，以及Tc后的a
            String newStr=str.substring(0,indexOfT-1)+str.substring(indexOfT,indexOfRightA);
            return isValid(newStr);
        }
    }
}

题解2

在网上找到的，其实和我的一样，都是找规律嘛，不过找到的规律不同。

aPbTc中a和b只能是若干个A或空字符串，且应满足length(a)*length(b)==length(c)&&length(b)>1。

代码如下：

import java.util.Scanner;

/**
 * PTABasicLevel 1003
 * https://pintia.cn/problem-sets/994805260223102976/problems/994805323154440192
 */
public class T1003 {
    public static void main(String[] args) {
        // 打开scanner
        Scanner scanner=new Scanner(System.in);

        // 用户输入的字符串
        String str=null;

        // 获取测试组数
        int T=scanner.nextInt();


        // T组测试
        while( T-- > 0){

            // 获取用户输入的字符串
            str=scanner.next();

            // 输出结果
            System.out.println(isValid(str)?"YES":"NO");
        }
        // 关闭scanner
        scanner.close();
    }

    /**
     * 判断一个字符串是否有效
     * @param str 一个字符串
     * @return 结果
     */
    public static boolean isValid(String str){

        // 字符串长度
        int strLength=str.length();

        // 字符串中P和T首次出现的位置
        int indexOfP=-1;
        int indexOfT=-1;

        // 字符串中P和T的数量
        int numOfP=0;
        int numOfT=0;

        // 字符串应仅由P、A、T组成，且P和T各有一个，判断过程中记录P和T的位置和个数
        for(int i=0;i<strLength;i++){
            // 存在PAT以外的字母，字符串就是错误的
            if(str.charAt(i)=='P'){
                indexOfP=i;
                numOfP++;
            }else if(str.charAt(i)=='T'){
                indexOfT=i;
                numOfT++;
            }else if(str.charAt(i)!='A'){
                return false;
            }
        }

        //在这一行，已知字符串仅由P、A、T组成

        if(numOfP==1&&numOfT==1&&indexOfT-indexOfP>1&&indexOfP*(indexOfT-indexOfP-1)==strLength-indexOfT-1){
            return true;
        }
        else{
            return false;
        }
    }
}

---

作者：@臭咸鱼

转载请注明出处：https://chouxianyu.github.io

欢迎讨论和交流!

---