题解 2309: 蓝桥杯2019年第十届省赛真题-人物相关性分析-滑动窗口算法

解题思路:
 

常规思想：两个不定长数组，j下标从0开始Alice找Bob，时间超限55

Bob运用数组方法：数组下标差的到的中间那段，找Bob为1的index有几个，然后相加，时间超限82

滑动窗口算法思想优化算法：循环Alice时候，下一次的Alice寻找Bob的开始和结束位置是上一次Alice的寻找Bob的开始和结束位置。

注意事项:sc.nextInt()和sc.nextLine()的结合使用时需要吞掉一个换行符。

参考代码:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int k=sc.nextInt();String kong=sc.nextLine();
		long count=0;
		String str=sc.nextLine();
		ArrayList<Integer> alice=new ArrayList<Integer>();
		ArrayList<Integer> bob=new ArrayList<Integer>();
		//int[] bob=new int[1000000];
		int froma=0,fromb=0;
		while(true){
			int indexa=str.indexOf("Alice",froma);
			froma=indexa+4;
			if(indexa==-1){froma=str.length()-1;}
			int indexb=str.indexOf("Bob",fromb);
			fromb=indexb+2;
			if(indexb==-1){fromb=str.length()-1;}
			if(indexa==-1&&indexb==-1){
				break;
			}
			if(indexa!=-1&&indexa+4<=str.length()-1){
				if((indexa+5==str.length()&&feizimu(str.charAt(indexa-1)))||(indexa==0&&feizimu(str.charAt(indexa+5)))||(feizimu(str.charAt(indexa-1))&&feizimu(str.charAt(indexa+5)))){
					alice.add(indexa);
				}
			}
			
			if(indexb!=-1&&indexb+2<=str.length()-1){
				if((indexb+3==str.length()&&feizimu(str.charAt(indexb-1)))||(indexb==0&&feizimu(str.charAt(indexb+3)))||(feizimu(str.charAt(indexb-1))&&feizimu(str.charAt(indexb+3)))){
					bob.add(indexb);
					//bob[indexb]++;
				}
			}
		}
		//int As = alice.size(), Bs = bob.size();       //As与Bs分别为两数组元素个数 
	    //int bl = 0, br = 0; 
		int j=0,m=0; 
		for(int i=0;i<alice.size();i++){
			/*int j=alice.get(i)-k-3;
			if(j<0){
				j=0;
			}
			int m=alice.get(i)+k+5;
			if(m>=str.length()){
				m=str.length()-1;            //此方法（Alice找Bob，Bob位置用下标定义）时间超限82
			}
			for(;j<=m;j++){
				if(bob[j]!=0){
					count++;
				}
			}*/
			
			/*while(bl < Bs && bob.get(bl)< alice.get(i) - k - 3)    bl++;   //维护窗口左边界 
	        while(br < Bs && bob.get(br) <= alice.get(i) + k + 5)   br++;   //维护窗口右边界 
	        count += br - bl;    */                     //下一次Alice的j和m都是从上一次的j和m开始，ac通过
			
			
			/*for(int j=0;j<bob.size();j++){
				if(bob.get(j)<alice.get(i)&&alice.get(i)-bob.get(j)<=k+3){
					count++;
				}
				if(bob.get(j)>alice.get(i)&&bob.get(j)-alice.get(i)<=k+5){
					count++;                       //j每次从0开始，时间超限82
				}
				if(bob.get(j)-alice.get(i)>k+5){
					break;
				}
			}*/
			
			for(;j<bob.size();j++){
				if(alice.get(i)-bob.get(j)<=k+3){
					break;
				}                           //下一次Alice的j和m都是从上一次的j和m开始，ac通过
				                          // 使用滑动窗口的算法思想来优化算法，否则将超时。
			}
			for(;m<bob.size();m++){
				if(bob.get(m)-alice.get(i)>k+5){
					break;
				}                 
			}
			count+=m-j;
		}
		System.out.println(count);
		
	}
	public static boolean feizimu(char ch){
		if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){
			return false;
		}else{
			return true;
		}
	}
}