任务相关分析
试题 H: 人物相关性分析
时间限制: 1.0s 内存限制: 512.0MB 本题总分:20 分
【问题描述】
小明正在分析一本小说中的人物相关性。他想知道在小说中 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 个字符。
注意:
1. Alice 和 Bob 是大小写敏感的,alice 或 bob 等并不计算在内。
2. Alice 和 Bob 应为单独的单词,前后可以有标点符号和空格,但是不能
有字母。例如 Bobbi 並不算出现了 Bob。
【输入格式】
第一行包含一个整数 K。
第二行包含一行字符串,只包含大小写字母、标点符号和空格。长度不超
过 1000000。
【输出格式】
输出一个整数,表示 Alice 和 Bob 同时出现的次数。
【样例输入】
20
This is a story about Alice and Bob. Alice wants to send a private message to Bob.
【样例输出】
2
【评测用例规模与约定】
对于所有评测用例,1 ≤ K ≤ 1000000。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class 人物相关分析 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String arr=sc.nextLine();
int k=Integer.valueOf(arr);
String str=sc.nextLine();
int count=0;
List<Integer> a=fangfa(str,"Alice");
List<Integer> b=fangfa(str,"Bob");
for (int i = 0; i < a.size(); i++) {
int aa=a.get(i);
for (int j = 0; j <b.size(); j++) {
int bb=b.get(i);
int cc=aa-bb;
if(cc>=-k-5&&cc<=k+3) {
count++;
}
}
}
System.out.println(count);
}
public static boolean isChar(char c) {
if(c>=97&&c<=122) {
return true;
}
if(c>=65&&c<=90) {
return true;
}
return false;
}
// 查找 出现的下标name
private static List<Integer> fangfa(String str, String name) {
// TODO Auto-generated method stub
int a=str.indexOf(name);
List<Integer> list=new ArrayList<Integer>();
while (a!=-1) {
char zuo=str.charAt(a-1);
char you=str.charAt(a+name.length());
if(isChar(zuo)||isChar(you)) {
}
else {
list.add(a);
a=str.indexOf(name,a+1);
}
}
return list;
}
}
- 点赞
- 收藏
- 关注作者
评论(0)