有几个PATjava答案

た入场券 2022-02-20 11:16 189阅读 0赞

一开始我觉得很简单，连续用了三层遍历，找到P后，再找A，再找T，这样很容易就超时了

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class Main{
      public static void main(String[] args) throws NumberFormatException, IOException{	  
    	  BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    	  String str=br.readLine();
    	  long count=0;//PAT的数量
    	  for(int i=0;i<str.length();i++) {
    		  if(str.charAt(i)=='P') {
    			  for(int j=i;j<str.length();j++) {
    				  if(str.charAt(j)=='A') {
    					  for(int m=j;m<str.length();m++) {
    						  if(str.charAt(m)=='T') {
    							  count++;
    						  }
    					  }
    				  }
    			  }
    		  }
    	  }
    	  System.out.print(count%1000000007);
      }
    }

下面介绍一种做法，先获取到字符串中所有T的数量，再对字符串逐个遍历，遍历到P，P的数量加1，遍历到T那么就把T的数量减1，因为这个T和P还没有A，如果遍历到A，就给total加上P的数量\*T的数量

import java.io.BufferedReader;
    import java.io.InputStreamReader;
    
    public class Main {
        public static void main(String[] args) throws Exception {
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            char[] s = in.readLine().toCharArray();
            in.close();
            int len = s.length, countp = 0, countt = 0;
            long total = 0;
            for (int i = 0; i < len; i++) {
                if (s[i] == 'T')
                    countt++;
            }
            for (int i = 0; i < len; i++) {
                if (s[i] == 'P')
                    countp++;
                if (s[i] == 'T')
                    countt--;
                if (s[i] == 'A') {
                    total = total + countp * countt;
                    if (total > 1000000007)
                        total = total % 1000000007;
                }
            }
            System.out.println(total);
        }
    }