PAT Advanced 1093. Count PAT’s (25) 同 PAT Basic 1040

NO IMAGE

注意:

        1、暴力搜尋會超時

思路:

        1、遍歷A,並記錄A左邊P的個數和右邊T的個數,記錄到陣列

Python程式碼(自己寫的,AC):

inputL  = list(raw_input())
listLen =len(inputL)
pCnt=0
tCnt=0
listP=[0]*listLen
listT=[0]*listLen
idxP=0
idxT=0
for i in xrange(listLen):
if inputL[i]=='P':
pCnt =1
elif inputL[i]=='A':
listP[idxP]=pCnt   
idxP =1
if inputL[listLen-1-i]=='T':
tCnt =1
elif inputL[listLen-1-i]=='A':
listT[idxT]=tCnt
idxT =1
count =0
for i in xrange(idxP):
count =listP[i]*listT[idxP-1-i]
count%=1000000007
print count

Java程式碼(自己寫的,思路相同,但部分超時):


import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
char[] arr =sc.nextLine().toCharArray();
int arrLen =arr.length;
int patCnt=0;
int[] pArr=new int[arrLen];
int[] tArr=new int[arrLen];
int cnt1 =0;
int cnt2 =0;
int pCnt=0;
int tCnt=0;
int i=0;
int j=0;
for(i=0;i<arrLen;i  ){
if(arr[i]=='P'){
cnt1  ;
}
else if(arr[i]=='A'){
pArr[pCnt  ]=cnt1;
}
j=arrLen-1-i;
if(arr[j]=='T'){
cnt2  ;
}
else if(arr[j]=='A'){
tArr[tCnt  ]=cnt2;
}
}
for(i=0;i<pCnt;i  ){
patCnt =pArr[i]*tArr[pCnt-1-i];
}
patCnt%=1000000007;
System.out.print(patCnt);
}
}

Python程式碼2(AC,自己寫的):思路也是遍歷A,但是記錄左右P和T的記錄方式不太一樣,這裡記錄的是P或T的累計量

inputLine = list(raw_input())
listLen =len(inputLine)
listP=[0]*listLen
listT=[0]*listLen
listP[0]= 1 if inputLine[0]=='P' else 0
listT[0]= 1 if inputLine[0]=='T' else 0
for i in  xrange(1,listLen):
listP[i]=listP[i-1]
listT[i]=listT[i-1]
if inputLine[i]=='P':
listP[i] =1
if inputLine[i]=='T':
listT[i] =1
count=0
for i in xrange(1,listLen):
if inputLine[i]=='A':
count  =listP[i-1]*(listT[listLen-1]-listT[i-1])
count%=1000000007
print count

參考:

http://blog.csdn.net/u013167299/article/details/44261891