当前位置: 首页 > 知识库问答 >
问题:

用递归法求0和1个数相等的最大子数组的长度

能帅
2023-03-14

给定一个只有01的数组,求取01数目相等的最大子数组的长度。例如,给定一个数组

011110001

编写递归函数largestsubarray。这个函数接受3个输入:一个数组-A,它的第一个元素的索引-start,最后一个元素的索引-end,并返回largestsubarray的大小。如果没有找到0和1数量相等的子数组,则函数应返回0。

int largestSubarray(int * A, int start, int end){
  int i, j=0, k=0;
  for(i=start; i<=end; i++){
    if(arr[i]==0){
     j++;
    }
    else if(arr[i]==1){
     k++;
    }
    if (j==k){
return (end+1-start)+largestSubarray(array, start+1, end);
    }

   }

如何修复此代码?请帮忙。谢了。

共有1个答案

嵇丰
2023-03-14

不清楚你是否解决了这个问题。递归可以为那些它唯一适合的任务提供优雅的解决方案,或者不能合理地编写过程解决方案的任务提供优雅的解决方案。每个递归调用都是一个单独的函数调用,需要一个完整的单独的函数堆栈。这会随着递归次数的增加而迅速消耗和耗尽可用内存。应优先采用程序解决办法

此外,数组011110001必须是包含以下值的数组的缩写

0, 1, 1, 1, 1, 0, 0, 0, 1

就其本身而言,0111100012396161的八进制常数。

在单个函数中,关键是强制返回每个递归调用,否则当递归函数展开时,您将遇到覆盖size的问题。一种实现方式可以是:

/* end must be ending index -- not size */
int largestsubarry (int *a, int start, int end)
{
    int o = 0, z = 0;       /* ones, zeros */

    if (end <= start)
        return 0;

    /* count the ones and zeros in subarray */
    for (register int i = start; i <= end; i++) {
        if (a[i] == 1)
            o++;
        else if (a[i] == 0)
            z++;
        else
            o = z = 0;      /* reset on any other value */
    }

    if (o != z) {   /* ones & zeros not equal */
        int s = largestsubarry (a, start + 1, end), /* test eliminating */
            e = largestsubarry (a, start, end - 1); /* each end */

        if (s > e)  /* return largest */
            return s;
        else
            return e;
    }
    else    /* balanced sub-array found, return size */
        return o + z;
}

(注意:虽然不是错误,但C的标准编码风格避免使用camelcasemixedcase变量名,而使用所有小写名,同时保留大写名用于宏和常量。这是一个风格问题--所以完全由您决定,但不遵循它可能会在某些圈子中导致错误的第一印象。)

示例使用/输出

传递包含以下值的整数数组将导致找到由顺序0和1组成的最大平衡子数组的适当大小,例如。

$ ./bin/subarray
enter array (ctrl+d ends): 0 1 1 1 1 0 0 0 1
size: 8

$ ./bin/subarray
enter array (ctrl+d ends): 1 1 0 1 1 1 1 0 0 0 1
size: 8

$ ./bin/subarray
enter array (ctrl+d ends): 1 1 0 1 1 1 1 0 0 0 1 0
size: 10

$ ./bin/subarray
enter array (ctrl+d ends): 1 1 0 1 0 0 0 0 0 0 1
size: 6

$ ./bin/subarray
enter array (ctrl+d ends): 0 2 2 2 2 0 0 0 2
size: 0

也许有更有效的方法来做这件事,但关键是知道要消除哪一端才能找到最长的平衡子数组。

 类似资料:
  • 我在一次采访中被问到这个问题。给定一个整数数组(具有正值和负值),我们需要找到具有相等总和的不相交子数组的最大数量。 例子: 输入:[1,2,3]输出:2{因为我们最多有2个子数组,总和=3,即[1,2],[3]} 输入: [2 2 2 -2] 输出 : 2 {两个子数组,每个子数组的总和 = 2,即 [2],[2, 2, -2]} 我的方法 我想到的第一种方法是找到前缀和数组,然后以每个元素(前

  • 那么我如何使用这个pair类和我的方法来找到最小值和最大值。

  • 子数组包含正数和负数。你必须找到一个最大和子数组,使子数组的长度大于或等于k。 下面是我用C++编写的使用Kadane算法的代码。 我的代码工作得很好,但很慢,我想不出任何方法来改进我的代码。我也读过这个问题,找到最长的子数组,它的和可以被K整除,但这不是我想要的,长度也可以大于K。

  • 如何加快以下问题陈述的执行速度?我有一个正确的解决方案,通过每一个测试的小输入。但是,它超过了较大输入的时间限制。我当前的实现是数组大小的二次型。 你的答案应该是基于1的,这意味着数组的第一个位置是1而不是0。 实施

  • O(n^2)算法简单。有没有人对此有更好的算法?

  • 我正在尝试编写递归方法,如果存在从[0]到[a.length-1]的路径,当您可以对a[I]求和或求减法时,该方法将返回true。例如,在数组a={2,4,1,6,4,2,4,3,5}中,该方法返回true,因为0 2-1 4 2-3 4=8=a[a.length-1]。我尝试了一些方法,但我得到了堆栈溢出或错误的输出。