给定一个只有0
和1
的数组,求取0
和1
数目相等的最大子数组的长度。例如,给定一个数组
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);
}
}
如何修复此代码?请帮忙。谢了。
不清楚你是否解决了这个问题。递归可以为那些它唯一适合的任务提供优雅的解决方案,或者不能合理地编写过程解决方案的任务提供优雅的解决方案。每个递归调用都是一个单独的函数调用,需要一个完整的单独的函数堆栈。这会随着递归次数的增加而迅速消耗和耗尽可用内存。应优先采用程序性解决办法。
此外,数组011110001
必须是包含以下值的数组的缩写
0, 1, 1, 1, 1, 0, 0, 0, 1
就其本身而言,011110001
是2396161
的八进制常数。
在单个函数中,关键是强制返回每个递归调用,否则当递归函数展开时,您将遇到覆盖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的标准编码风格避免使用camelcase
或mixedcase
变量名,而使用所有小写名,同时保留大写名用于宏和常量。这是一个风格问题--所以完全由您决定,但不遵循它可能会在某些圈子中导致错误的第一印象。)
示例使用/输出
传递包含以下值的整数数组将导致找到由顺序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]。我尝试了一些方法,但我得到了堆栈溢出或错误的输出。