PAT——有几个PAT

思路来源：https://www.cnblogs.com/asinlzm/p/4440603.html

字符串APPAPT中包含了两个单词“PAT”，其中第一个PAT是第2位(P),第4位(A),第6位(T)；第二个PAT是第3位(P),第4位(A),第6位(T)。

现给定字符串，问一共可以形成多少个PAT？

输入格式：

输入只有一行，包含一个字符串，长度不超过10⁵，只包含P、A、T三种字母。

输出格式：

在一行中输出给定字符串中包含多少个PAT。由于结果可能比较大，只输出对1000000007取余数的结果。

输入样例：

APPAPT

输出样例：

核心思路：如果有一个P出现，则只要知道后面有多少种AT可选，则这个P可以对应的PAT选择方法就有多少种；AT类似。

啰嗦思路：组成PAT的条件有P在A前出现，A在T前出现。
求PAT选择的方法有多少种，则只要知道每个P对应的PAT选择方法有多少种，求和即可；
每个P对应PAT种类取决于这个P的后面，有多少种AT可选（如果有一个P出现，则只要知道后面有多少种AT可选，则这个P可以对应的PAT选择方法就有多少种）。

一个P后面有多少种AT可选，其实和这个字符串中多少种PAT可选是一个问题，即所有的A对应的AT选法的和；
一个A对应的AT种类取决于这个A后面有多少种T可选（如果有一个A出现，则只要知道后面有多少种T出现，则这个A对应的AT选择方法就有多少种）。

eg：PPPAATTT
字符： P P P A A T T T
位置： 7 6 5 4 3 2 1 0

下标为7的P对应的PAT选法取决于后面字符串（PPAATTT）中AT的选法，其他P相应对应自己后面的字符串的AT选法；
下标为4的A对应的AT选法取决于后面字符串（ATTT）中的T的选法，另一个A相应处理；
下标为2/1/0的T进行不需要选择了，因为一个T对应的T的选法就是自身；
代码变量说明：
numAT表示当前已处理的字符串字串中T的选法，也就表明，如果处理一个字符是A，则这个字符A对应的AT的选法，就是numAT；
numPAT的理解相对应。
手工流程演示：位于下标5的P对应的PAT的选法有6种，来源于P后面的两个A，下标4的A对应的AT有3种选法，下标3的A也是。

 package com.hone.basical;

 import java.util.Scanner;

 /**

  * 原题目：https://www.patest.cn/contests/pat-b-practise/1039

  * @author Xia

  * 利用递归来处理！！！！

  */

 public class basicalLevel1040howManyPat {

     public static void main(String[] args) {

         Scanner in = new Scanner(System.in);

         char[] pat = in.nextLine().toCharArray();

         int len = pat.length;

         in.close();

         int numPat = 0,numAt = 0, num = 0 ;

         //从后面往前面遍历

         while((len--)>0){

             if (pat[len] == 'T') {

                 numAt++;

             }else if (pat[len] == 'A') {

                 numPat+=numAt;

             }else {

                 num+=numPat;

                 //因为输出的结果具有周期性，所以可以提前处理，当参数大于指定的次数的时候

                 //可以先取余数

                 if (num > 1000000007) {

                     num = num%1000000007;

                 }

             }

         }

         System.out.println(num);

     }

 }

巴特西

PAT——有几个PAT

最新文章

热门文章