1.H题 人物相关性分析

• 样例输入

  20 This is a story about Alice and Bob. Alice wants to send a private message to Bob.

• 样例输出

  2

1.1思路分析

本题主要运用了滑动窗口的算法技巧，首先，定义两个数组分别用来存储Alice和Bob出现的位置下标。遍历字符串的时候，要注意题目中“单独的单词”的要求，也就是说，在每一个可能的单词位置下标，我们事先都要判断该位置的前一个位置和下标+单词长度的位置是否是字母，只有满足两个位置都不是字母，才能说明这个下标开始的单词是一个单独的单词。
储存好了所有的数据以后，我们以Alice【】数组为遍历对象，我们定义一个滑动窗口，刚开始，窗口的左边界和又边界都在0位置，初始遍历指针为0。根据题意“同时出现”我们可以知道，Bob可以出现在Alice的前面和后面，由此可以推断出Bob位置的范围。
我们滑动窗口维护的就是满足该条件的左右边界，刚开始检查Bob[right]是否在该范围内，如果不在该范围内则left++，直到满足该条件，然后再检查Bob[right]是否在这个范围内，如果不在这个范围内，则right++（这样的两个指针的移动，就好像一个窗口的扩张和收缩），第一次窗口的左右边界确定以后，最终的[left,right],符合”A”-“B”之间距离差<=K的个数就是 = right - left。
（理解的难点）第一次Bob【right】遍历的时候把包括Bob[left]遍历的包括了进去，这时减去Bob[left]的数量，剩下的就是在这个范围内符合要求的组合单词数量。

1.2代码

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Main3 {
    static String s;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        sc.nextLine();// 吞掉回车
        s = sc.nextLine();
        List<Integer> Alice = new LinkedList<Integer>();
        List<Integer> Bob = new LinkedList<Integer>();
        int ans = 0;
        // 检查Alice
        for (int i = 0; i + 5 <= s.length(); i++) {
            if ((i == 0 || !check(i - 1)) && (i + 5 == s.length() || !check(i + 5))) {
                // 满足条件：是一个单独的单词。
                if (s.substring(i, i + 5).equals("Alice")) {
                    Alice.add(i);
                    // i += 5;// 剪枝操作
                }
            }
        }
        // 检查Bob
        for (int i = 0; i + 3 <= s.length(); i++) {
            if ((i == 0 || !check(i - 1)) && (i + 3 == s.length() || !check(i + 3))) {
                if (s.substring(i, i + 3).equals("Bob")) {
                    Bob.add(i);
                    // i += 3;// 剪枝操作
                }
            }
        }
        // 利用滑动窗口维护限定范围内的符合要求的单词数量
        for (int i = 0, l = 0, r = 0; i < Alice.size(); i++) {
            while (r < Bob.size() && Bob.get(r) <= Alice.get(i) + K + 5) {
                r++;
            }
            while (l < Bob.size() && Bob.get(l) < Alice.get(i) - K - 3) {
                l++;
            }
            ans += r - l;
        }
        System.out.println(ans);
    }
    public static boolean check(int i) {
        return (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') || (s.charAt(i) >= 'a' && s.charAt(i) <= 'z');
    }// 如果是字母，就返回true;
}