Keshawn_lu's Blog

PAT 1040.有几个PAT

字符串
字数统计: 327阅读时长: 1 min
2021/02/10 Share

题目简介：

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

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

输入格式：

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

输出格式：

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

输入样例：

1
APPAPT

输出样例：

1
2

思路：

从前往后遍历，PA的数量为当前A之前P的数量，PAT的数量为当前T之前PA的数量。

最后累加的PAT数量即为结果。

tip:

  • 需要在累加过程中对P,PA,PAT进行取余操作

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <iomanip>

using namespace std;


int main()
{
	string str;
	cin >> str;

	int P = 0;
	int PA = 0;
	int PAT = 0;
	for (int i = 0; i < str.size(); i++) {

		if (str[i] == 'P')
			P++;
		else if (str[i] == 'A')
			PA = (PA + P) % 1000000007;	//累加 这个A之前P的数量
		else
			PAT = (PA + PAT) % 1000000007;	//累加 这个T之前PA的数量
	}

	cout << PAT;
}
CATALOG
  1. 1. 题目简介：
    1. 1.1. 输入格式：
    2. 1.2. 输出格式：
    3. 1.3. 输入样例：
    4. 1.4. 输出样例：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网