题目描述
原题连接:https://www.acwing.com/problem/content/description/3178/
小明正在分析一本小说中的人物相关性。
他想知道在小说中 Alice 和 Bob 有多少次同时出现。
更准确的说,小明定义 Alice 和 Bob “同时出现”的意思是:在小说文本中 Alice 和 Bob 之间不超过 K
个字符。
例如以下文本:
This is a story about Alice and Bob. Alice wants to send a private message to Bob.
假设 K=20
,则 Alice 和 Bob 同时出现了 2
次,分别是 Alice and Bob 和 Bob. Alice。
前者 Alice 和 Bob 之间有 5
个字符,后者有 2
个字符。
注意:
Alice 和 Bob 是大小写敏感的,alice 或 bob 等并不计算在内。
Alice 和 Bob 应为单独的单词,前后可以有标点符号和空格,但是不能有字母。例如 Bobbi 並不算出现了 Bob。
输入格式
第一行包含一个整数 K
。
第二行包含一行字符串,只包含大小写字母、标点符号和空格。长度不超过 1000000
。
输出格式
输出一个整数,表示 Alice 和 Bob 同时出现的次数。
数据范围
1≤K≤1000000
输入样例:
20
This is a story about Alice and Bob. Alice wants to send a private message to Bob.
输出样例:
2
滑动窗口解法
这题不是很难,就是麻烦,要处理间隔,要单独出现,还要判断两个人的长度....
直接用滑动窗口肯定不行,但如果能找出所有符合题意的Alice和Bob的位置,再去找出有多少个距离不大于k得位置,那就是一道滑动窗口模板题了。
这种题多分几个模块就好写
时间复杂度 O(N)
Java代码
import java.util.Scanner;
public class 人物相关性分析 {
static int maxN = 1000000;
static char[] chars;
static char[] Alice = {'A', 'l', 'i', 'c', 'e'};
static char[] Bob = {'B', 'o', 'b'};
static int[][] index = new int[maxN / 3][2]; //记录每个人物的位置。数组0位置是在原数组中的索引。1位置是类型->0:Alice,1:Bob。
static int size; //有多少个符合的Alice和Bob
static int[] len = {5, 3}; // Alice和Bob的长度,用于滑动窗口长度的判断
static int k;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
k = sc.nextInt();
sc.nextLine();
chars = sc.nextLine().toCharArray();
//找到所有符合题意得Alice和Bob下标,并放入index数组中
for (int i = 0; i < chars.length; i++) {
if (!check(i)) {
//如果当前字符是字母,则跳到下一个不是字母的地方
while (i < chars.length && !isSymbol(i)) {
i++;
}
continue;
}
index[size][0] = i;
index[size++][1] = chars[i] == 'A' ? 0 : 1;
}
int[] count = new int[2]; //记录当前窗口中Alice和Bob出现的次数。0表示Alice出现的次数,1表示Bob
long res = 0; //不开long gg
//滑动窗口
for (int i = 0, j = 0; j < size; j++) {
count[index[j][1]]++;
while (i < j && index[j][0] - index[i][0] - len[index[i][1]] > k) { //窗口不能>k。减去len是减去单词的长度
count[index[i++][1]]--;
}
//在窗口不>k的情况下,是否同时出现过
if (count[0] > 0 && count[1] > 0) {
if (index[j][1] == 0) { //加上窗口内对方出现的次数
res += count[1];
} else {
res += count[0];
}
}
}
System.out.println(res);
}
public static boolean check(int i) {
if (chars[i] == 'A') {
for (int j = 0; j < 5; j++) {
if (i + j >= chars.length || chars[i + j] != Alice[j]) {
return false;
}
}
int next = i + 5;
if (next > chars.length) return false;
return next == chars.length || isSymbol(next);
} else if (chars[i] == 'B') {
for (int j = 0; j < 3; j++) {
if (i + j >= chars.length || chars[i + j] != Bob[j]) {
return false;
}
}
int next = i + 3;
if (next > chars.length) return false;
return next == chars.length || isSymbol(next);
}
return false;
}
public static boolean isSymbol(int i) {
char c = chars[i];
if (c >= 'a' && c <= 'z') return false;
if (c >= 'A' && c <= 'Z') return false;
return true;
}
}