1040 有几个PAT(25)

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

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

输入格式：

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

输出格式：

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

输入样例：

APPAPT

输出样例：

Solution:

先用最暴力的方法求解， 1,2AC, 后三个超时, 15分, 如何解决3sum问题?

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;

int main() {
  string s; cin >> s;
  int n = s.length(), cnt = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == 'P') {
      for (int j = i+1; j < n; j++) {
        if (s[j] == 'A') {
          for (int k = j+1; k < n; k++) {
            if (s[k] == 'T') {
              cnt++;
            }
          }
        }
      }
    }
  }
  printf("%d\n", cnt ? cnt % 1000000007 : 0);
  return 0;
}

其实这道题目跟3sum问题还是有区别, 是属于观察特性, 总结规律的题目.

对于每一个A来说, 可以跟它组合个数是, 前面P的个数*后面T的个数.

给出一种新的解法。

// 计算每个A左边有几个P, 右边有几个T, 相乘
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;

int main() {
  string s; cin >> s;
  int sum = 0, n = s.length();
  for (int i = 0; i < n; i++) {
    if (s[i] == 'A') {
      int left_P = 0, right_T = 0;
      int p = i-1, q = i+1;
      while (p >= 0) {
        if (s[p] == 'P') left_P++;
        p--;
      }
      while (q < n) {
        if (s[q] == 'T') right_T++;
        q++;
      }
      sum += left_P * right_T;
    }
  }
  printf("%d\n", sum);
  return 0;
}
// case3, 4, wrong

但这个复杂度, 仍然后很高, 因为找过的p又重新找了。

我在外公家用他的麻将牌模拟了一遍, 找出一种新解法。
既然是需要左边的P, 右边的T, 如果从左往右扫描的话, 先用一次扫描记录字符串所有T的个数right_t, 只要在下次扫描过程中, 用left_p记录从左边到A所有P的个数, 碰到T之后, right_t减1, 碰到A就左右相乘

坑点, 每次相加就需要取余数, 这里有点理不清楚, 但是先这样理解着吧。

// 优化递推的做法,
// Time: O(n), Space:O(1)

#include <iostream>
#include <string>
using namespace std;

int main() {
  string s; getline(cin, s);
  int sum = 0, cnt_p = 0, cnt_t = 0;
  int n = s.length();
  for (int i = 0; i < n; i++) {
    if (s[i] == 'T') cnt_t++;
  }
  for (int i = 0; i < n; i++) {
    if (s[i] == 'P') {
      cnt_p++;
    } else if (s[i] == 'T') {
      cnt_t--;
    } else if (s[i] == 'A') {
      sum = (sum + cnt_p * cnt_t) % 1000000007;
    }
  }
  cout << sum << endl;
  return 0;
}