在 Java 中使用递归查找字符串“BBA”在字符数组中的频率

Question

递归方法练习：

使用分治技术编写 Java 方法 int findBBA(char[] array, int left, int 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;
}

Answer 1

你把这个任务搞得太复杂了。在方法的最开始声明并初始化

res

为

0

：

int res = 0;

您的递归方法有一个

left

和

right

参数。由于它们没有声明为 final ，您显然可以在方法中使用和修改它们的值。不需要

mid

变量，因为

left + 1

将为您提供该信息。

您的方法中实际上应该只需要一个主要

if

块和另一个

if

块来检查

right

是否超出了

array.length - 1

:

if (array[left] == 'B' && array[left + 1] == 'B' && array[right] == 'A') {
    System.out.println("BBA sequence found at array index: " + left);
    res = 1;
}

// Increment parameter values so to continue checking the array:
left += 1;   // Increment `left` by 1
right += 1;  // Increment `right` by 1

/* If `right` has gone beyond array.length - 1 then 
   you've reached the end of the array.  */
if (right > array.length -1) {
    return res;
}
// Otherwise...recursively call this method again with new argument values
else {
    res = res + findBBA(array, left, right);
    // or:  res += findBBA(array, left, right);
}
return res;

要使用你可能会有这样的东西：

char[] array = {'D','B','B','A','C','B','B','A','F','G','A','B','B','C','B','B','A'};
int fnd = findBBA(array, 0, 2);
System.out.println("BBA sequence is within the array at " + fnd + " locations.");

控制台输出应如下所示：

BBA sequence found at array index: 1
BBA sequence found at array index: 5
BBA sequence found at array index: 14
BBA sequence is within the array at 3 locations.