Love丶FFC's Blog

PAT乙级:1040 有几个PAT

2020-03-02 04:42:19
阅读:557   •   评论:9
标签:,

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

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

输入格式:

输入只有一行,包含一个字符串,长度不超过10​5​​,只包含 PAT 三种字母。

输出格式:

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

输入样例:

APPAPT

输出样例:

2

编程语言:Python

解题思想:

如果使用多层循环来进行判断,会导致超时,因此需要思考一个优化算法

1.例如PPPPAAAATTTT,对于每个A来说有4个P,对于每个T来说有16个PA,因此可以构成16*4个PAT

2.遍历字符串,每找到一个T就记录一次,每找到一个A就累加T,每找到一个P就累加AT

时间复杂度:O(N)

代码如下:

  1. String = input() # 输入字符串
  2.  
  3. P = 0
  4. PA = 0
  5. PAT = 0
  6.  
  7. for i in range(0, len(String)):
  8. if String[i] == 'P':
  9. P += 1
  10. elif String[i] == 'A':
  11. PA += P
  12. elif String[i] == 'T':
  13. PAT += PA
  14. print(PAT % 1000000007)

评论板

共有 9 条评论

  1. fruinly

    b; Kalariya et al buy cialis online no prescription pdf casks cialis and viagra pack These results have not been published in a peer- reviewed scientific journal

  2. engarma

    Thus, the US FDA does not recommend withholding opioid replacement therapy in the context of other sedating medications; cautious medication management is advised buy priligy 60

  3. cheap louis vuitton bags

    I just wanted to thank you for the fast service. as well they look great. I received them a day earlier than expected. prefer the I will definitely continue to buy from this site. regardless I will recommend this site to my friends. Thanks!
    cheap louis vuitton bags https://www.louisvuittonsoutletstore.com/

  4. cheap louis vuitton online

    I just wanted to thank you for the fast service. in addition they look great. I received them a day earlier than expected. particularly the I will definitely continue to buy from this site. blue jays I will recommend this site to my friends. Thanks!
    cheap louis vuitton online https://www.bestlouisvuittonoutlet.com/

  5. cheap jordans online

    I just wanted to thank you for the fast service. and also they look great. I received them a day earlier than expected. just like the I will definitely continue to buy from this site. blue jays I will recommend this site to my friends. Thanks!
    cheap jordans online https://www.realjordansretro.com/

  6. cheap louis vuitton bags

    I just wanted to thank you for the fast service. or possibly they look great. I received them a day earlier than expected. for example the I will definitely continue to buy from this site. in any event I will recommend this site to my friends. Thanks!
    cheap louis vuitton bags https://www.cheapreallouisvuitton.com/

  7. louis vuitton outlet

    Read reviews and was a little hesitant since I had already inputted my order. and even but thank god, I had no issues. similar to the received item in a timely matter, they are in new condition. regardless so happy I made the purchase. Will be definitely be purchasing again.
    louis vuitton outlet https://www.louisvuittonsoutletonline.com/

  8. Preliaf

    Management is complex in these cases, and in the authors experience, survival is more limited priligy reddit

  9. Preliaf

    These vibrations cause the three tiny bones in the middle ear to move, transmitting the sound to the inner ear levitra comprimes

--------查看该分类下最新文章--------
^
新版博客正在完善中!域名:http://www.loveffc:8080,点击跳转,完全移植后将去除端口号。

Copyright © 2018 - 2021 FFC的小站 - 滇 ICP 备 18010780 号 - 1

- Powered by WordPress & AliYun · Theme by FFC -

- Environment by Windows & XAMPP · Designed by WebStorm & VSCode -

已运行:

访问量:456920