java - 如何管理递归函数？

Question

我需要编写一个获取 4 个参数的递归函数。

第一个是数组。第 2 个是左索引，第 3 个是右索引和“K”索引。 “K”索引是 array 中的一个单元格，lrft 索引指向开始，右侧索引指向结束。

数组可以包含诸如零和一之类的洋地黄。该方法返回包含单元格 k 的序列的最大长度。

这是我需要获得的结果的示例:

public static void main(String[] args) {
   int[] A = {1,1,1,0,1,1,0,1,1,1,1,1,0,1,1};
   System.out.println(floodOnes(A,0, A.length-1, 9)); // 5 output
   System.out.println(floodOnes(A,0, A.length-1, 3)); // 0 output
   System.out.println(floodOnes(A,0, A.length-1, 0)); // 3 output
   System.out.println(floodOnes(A,0, A.length-1, 14)); // 2 output
}

public static int floodOnes(int [] A,int left, int right, int k){
    //some logic
}

这是我的实现:

public class Program {
    public static void main(String[] args) {
        int[] A = {1,1,1,0,1,1,0,1,1,1,1,1,0,1,1};
        System.out.println(floodOnes(A,0,A.length-1, 9));
    }

    public static int floodOnes(int [] A,int left, int right, int k){           
        if (left != k) left+=1;
        if (right != k) right-=1;   

        if (left == k  && right == k) return A[k]; //condition when the recursive call stops 

        int res = floodOnes(A, left,  right,  k);

        if (A[left] == 1 && A[right] == 1) 
            return res = A[left] + A[right];  //count ones      

        else  return res;   
    }   
}

但是我的解决方案无法正常工作。

在此行中:

if (A[left] == 1 && A[right] == 1) 
      return res = A[left] + A[right];  //count ones  

如果其中一个条件没有执行一次，则后面的返回不应将 1 添加到结果变量中。

我不知道该怎么做。

Answer 1

我证明我的评论是错误的。这是一个递归方法，带有问题中提到的4个参数，确实解决了问题。

public static int floodOnes(int[] a, int left, int right, int k) {
    if (0 <= left && left <= k && k <= right && right < a.length) {
        // is there a 0 between left (inclusive) and k (exclusive)?
        int i = left;
        while (i < k && a[i] == 1) {
            i++;
        }
        if (i < k) {
            assert a[i] == 0;
            return floodOnes(a, i + 1, right, k);
        }
        // is there a 0 between k (exclusive) and right (inclusive)?
        i = right;
        while (i > k && a[i] == 1) {
            i--;
        }
        if (i > k) {
            assert a[i] == 0;
            return floodOnes(a, left, i - 1, k);
        }
        // no zero found, a[k] not checked, though
        if (a[k] == 0) {
            return 0;
        } else {
            return right - left + 1;
        }
    } else {
        throw new IllegalArgumentException("Expected " + left + " <= " + k + " <= " + right + " < " + a.length);
    }
}

使用此方法，问题中的第一个 main 方法将打印预期的内容:

5
0
3
2

我真的不认为以这种方式解决问题有什么意义，所以我很不确定这是否是我们的意图。我更喜欢非递归解决方案，或者如果它只需要以某种方式递归，那么 Grzegorz Górkiewicz’ answer 中的解决方案.