如何用分治法递归实现Java方法统计字符数组中"BBA"的出现次数

练习要求 #

使用分治法（divide-and-conquer）编写Java方法 int findBBA(char[] array, int left, int right)，返回字符数组中从left到right范围内（左闭右开区间）字符串"BBA"的出现次数。

问题描述 #

我只会解决统计双字符序列的类似问题（比如统计整数数组中"01"或字符数组中"BA"的出现次数），查了资料也找不到这个三字符序列问题的分治解决方案，求大家帮忙，非常感谢。

我尝试的代码 #

public static int _findBBA(char[] a, int l, int r) {
    
    if(l+2 >= r)

        return 0;
    
    int mid = (l+r)/2;
    
    int find1 = _findBBA(a, l, mid);
    int find2 = _findBBA(a, mid, r);
    
    int res = find1 + find2;
    
    if(a.length % 2 == 0) {
    
        if(a[mid-1] == 'B' && a[mid] == 'B' && a[mid+1] == 'A')
            res++;
        
        if(a[mid-2] == 'B' && a[mid-1] == 'B' && a[mid] == 'A')
            res++;
    }
    
    else
        if(a[mid-1] == 'B' && a[mid] == 'B' && a[mid+1] == 'A')
            res++;
    
    return res;
}

问题分析与修正代码 #

你的代码存在几个关键问题：

1. 数组越界风险：判断跨区间情况时未检查mid-2、mid+1等下标是否在当前处理的区间范围内，容易触发数组越界异常。
2. 错误依赖数组整体奇偶性：当前处理的子区间和整个数组的奇偶性无关，以此作为判断条件完全不合理。
3. 跨区间逻辑不严谨：没有根据子区间的实际长度判断是否可能形成跨区间的"BBA"。

分治法的核心逻辑是：将区间拆分为左右子区间，分别统计子区间内的"BBA"次数，再统计跨左右子区间的"BBA"次数，三者相加即为总次数。

跨区间的"BBA"只有两种可能：

• 左子区间的最后两个字符是"BB"，右子区间的第一个字符是"A"，组合成"BBA"
• 左子区间的最后一个字符是"B"，右子区间的前两个字符是"BA"，组合成"BBA"

修正后的代码如下：

public static int findBBA(char[] array, int left, int right) {
    // 区间长度不足3，无法组成"BBA"，直接返回0
    if (right - left < 3) {
        return 0;
    }
    
    // 避免溢出的中点计算方式
    int mid = left + (right - left) / 2;
    // 递归统计左右子区间的"BBA"次数
    int leftCount = findBBA(array, left, mid);
    int rightCount = findBBA(array, mid, right);
    
    int crossCount = 0;
    
    // 检查第一种跨区间情况：左区间最后2个字符 + 右区间第1个字符 = "BBA"
    if (mid - left >= 2 && right - mid >= 1) {
        if (array[mid-2] == 'B' && array[mid-1] == 'B' && array[mid] == 'A') {
            crossCount++;
        }
    }
    
    // 检查第二种跨区间情况：左区间最后1个字符 + 右区间前2个字符 = "BBA"
    if (mid - left >= 1 && right - mid >= 2) {
        if (array[mid-1] == 'B' && array[mid] == 'B' && array[mid+1] == 'A') {
            crossCount++;
        }
    }
    
    // 总次数 = 左区间次数 + 右区间次数 + 跨区间次数
    return leftCount + rightCount + crossCount;
}

代码说明 #

• 边界处理：当区间内字符数小于3时，直接返回0，因为无法形成三字符的"BBA"。
• 分治拆分：用left + (right - left)/2计算中点，避免整数溢出问题。
• 跨区间统计：分别检查两种可能的跨区间组合，同时判断左右区间的长度是否满足组合条件，从根源避免数组越界。
• 结果合并：将左右子区间的次数与跨区间次数相加，得到当前区间的总次数。

内容的提问来源于stack exchange，提问作者Francesco Pandolfo