我在试着解决一个问题,但是我的记忆力已经超过了极限。
问题描述
给定一个整数数组A和两个整数B和C。
你需要找出B出现的次数等于C出现的次数的子数组的个数。
注意:不要计算空的子数组。
输入格式第一个参数是整数数组A。
第二个参数是整数B。
第三个参数是整数C。
输出格式返回一个整数,表示B出现的次数等于C出现的次数的子数组的数量。
/**
* @input A : Integer array
* @input n1 : Integer array's ( A ) length
* @input B : Integer
* @input C : Integer
*
* @Output Integer
*/
int SubArrays(int* arr, int start, int end, int size, int B, int C)
{
int countB = 0,countC = 0;
// Stop if we have reached the end of the array
if (end == size)
return 0;
// Increment the end point and start from 0
else if (start > end)
SubArrays(arr, 0, end + 1, size, B, C);
// Print the subarray and increment the starting point
else {
int A[end-start+1];
int i, j;
for ( i = start; i < end; i++){
for(j =0; j<(end-start+1);j++){
A[j] = arr[i];
}
}
for(j =0; j<(end-start+1);j++){
if(A[j]==B) countB ++;
if(A[j]==C) countC ++;
}
// cout << arr[end] << "]" << endl;
SubArrays(arr, start + 1, end, size, B, C);
}
if(countB == countC)
return 1;
else
return 0;
}
int solve(int* A, int n1, int B, int C) {
int count = 0;
count = count + SubArrays(A,0,0,n1,B,C);
return count;
}
1条答案
按热度按时间ndasle7k1#
在一般情况下,您的例程创建一个数组
int A[end-start+1]
,然后递归地调用它自己。这会占用很多空间,而且没有必要。许多挑战或在线评判问题旨在创造性地解决,使用问题的“更大”视图,而不是“蛮力”,例如检查所有可能的组合。
在这种情况下,解决方案是:
| * 我 *| 0| 1| 2| 3| 4| 5个|六|七个|八|
| - -----|- -----|- -----|- -----|- -----|- -----|- -----|- -----|- -----|- -----|
| 一个|1| 3| 3| 5个|4| 0| 4| 4| 4|
| T型|0| +1| +2| +2| +1| +1| 0| −1| −2|
例如,利用上述,(0,6)(意味着 i=0,j=6)形成具有相等数量的 B 值和 C 值的子阵列,并且(1,4)、(1,5)、(2,3)和(4,5)也是如此。因此,所需的子阵列数量为5。
(If如果允许修改原始数组,则可以在数组中就地计算该辅助信息,替换其原始内容。
这将给予你一个解决方案,所需时间大致与 n2成正比,其中 n 是A中元素的数量。但是,有一个更好的解决方案:
这给出了一个运行时间大致与 n log n 成比例的解决方案。
它可以在一个函数中实现,其中包含七行C代码(利用一些有经验的程序员可能使用的C符号,但合理)和一个辅助函数(用于排序比较),只有一行或两行。
计数对的提示:您不需要等到重复序列结束才添加到运行总数中。如果T中的当前值到目前为止已经出现了 m 次,则将 m−1添加到运行总数中。当该值被看到 m 次时,将为它们添加 m·(m−1)。例如,如果一个值被看到四次,我们将在第一次看到它时添加0,然后是1,然后是2,然后是3,1+2+3 = 4·(4−1)/2。