问题描述

renwu

思路

（1）暴力

刚开始做时，因为在输入时通过正则表达式分隔字符串比较方便，所以一直在想分割后的办法…

常规解法：遍历字符串，找到Alice和Bob的起点位置分别放入到一个集合中，分别遍历两个集合，找到K范围内前面匹配的目标的个数。提交然后超时了，不过能过70分的样例哈哈哈哈🤣🤣

（2）滑动窗口

同上，先遍历一遍字符串，将Alice和Bob的起始索引分别放到两个集合中

遍历Alice的集合，利用双指针维护一个指定范围的窗口，找到每个Alice在自身索引±K\pm K范围内的Bob索引个数即可。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

/**
 * @author duanqihang
 * Created with IntelliJ IDEA.
 * User: suse_QiHang
 * Date: 2022/4/1 15:00
 * Description: 双指针
 */
public class 人物相关性分析_改进 {
    static int K;
    static long result; //数据量比较大
    static void solve(String str){
        ArrayList<Integer> alist = new ArrayList<>();
        ArrayList<Integer> blist = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            if(str.charAt(i) == 'A' && str.startsWith("Alice", i)) alist.add(i);
            if(str.charAt(i) == 'B' && str.startsWith("Bob", i)) blist.add(i);
        }

        int bl = 0, br = 0;//滑动窗口的左右边界
        for (Integer integer : alist) {
            //维护窗口左边界
            while (bl < blist.size() && blist.get(bl) < integer - K - 3) bl++;
            //维护窗口右边界
            while (br < blist.size() && blist.get(br) <= integer + K + 5) br++;
            result += br - bl; //当前Alice窗口内Bob索引的数量
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        K = Integer.parseInt(read.readLine().trim());
        solve(read.readLine().trim());
        System.out.println(result);
    }
}

总结

双指针类问题印象较少可能是以前遇到并没有用双指针求解，特此记录！