PAT——1040. 有几个PAT-白红宇

PAT——1040. 有几个PAT

阅读量：463 次

发布时间：2019-03-06

本文共 1287 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要计算给定字符串中包含多少个“PAT”序列。每个“PAT”序列中的字母P、A、T必须按顺序出现，但不需要连续。

方法思路

我们可以通过从左到右遍历字符串的方式来高效地计算满足条件的“PAT”序列的数量。具体步骤如下：

维护变量：我们需要三个变量来跟踪当前遇到的P的数量、P和A组合的数量以及最终的“PAT”序列的数量。

遍历字符串：从左到右遍历每个字符：

如果遇到P，增加P的计数。

如果遇到A，增加P和A组合的计数。

如果遇到T，则增加最终的“PAT”序列计数。

结果处理：由于结果可能非常大，我们对结果取模1000000007。

这种方法的时间复杂度是O(n)，适用于长度很大的字符串。

解决代码

public class basicalLevel1040howManyPat {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] pat = in.nextLine().toCharArray();
        int len = pat.length;
        int pCount = 0, paCount = 0, result = 0;
        for (int i = 0; i < len; i++) {
            char c = pat[i];
            if (c == 'P') {
                pCount++;
            } else if (c == 'A') {
                paCount += pCount;
            } else if (c == 'T') {
                result += paCount;
                // 取模操作
                if (result >= 1000000007) {
                    result %= 1000000007;
                }
            }
        }
        // 在最后，确保结果取模
        result %= 1000000007;
        System.out.println(result);
        in.close();
    }
}