我试图在技术面试的在线评估中解决以下问题，但失败了。 我已经思考这个问题一段时间了，似乎找不到让我满意的答案：
您正在寻找数组 A 的最长前导片段(前缀(，其中 X 和 Y 的出现次数相等，其中 X 和 Y 是整数。
例如，在 X=7 和 Y=42 中，A=[6， 42， 11， 7， 1， 42] 的最长前缀为 4，因为 A[0]-A[4] 包含相同数量的 X 和 Y。
另一个例子，X=6 和 Y=13。 A=[13,13,1,6]。 该函数应返回 -1，因为没有前缀。
X=100、Y=63 和 A=[100,63,1,6,2,13] 应返回 5。
我尝试用 C 语言回答：
int solution(int X, int Y, int A[], int N){
int result=-1;
int nX=0; //number of occurrences of X
int nY=0; //number of occurrences of Y
int i;
for(i=0;i<N;i++){//loop through the input array
if(A[i]==X)//occurrence of X
nX += 1;
/*
EDGE CASE BELOW: this should have been an if
statement, because X and Y could be the same
number. I know I missed this in the assessment,
but believe there is another issue, because I
failed almost all the test cases generated by the
assessment.
*/
else if(A[i]==Y)//occurrence of Y
nY += 1;
if((nX!=0)&& (nX==nY))//same number of X and Y
//and there is at least one occurence of each
result=i;//longest prefix is the index
}
return result;
}
不幸的是，我自己无法生成失败的测试用例，并且失败的测试用例隐藏在评估中。因此，我无法提供太多有用的信息。
我知道，每次失败时，我的程序都会返回 -1 而不是正确答案。
如果你们中的任何人通过思考就能看到错误，我很想看看我错过了什么。 谢谢！
如果您准确地描述了要求，则它们不会指定X和Y出现的正数。零有效。
所以这个：
if((nX!=0)&& (nX==nY))//same number of X and Y
//and there is at least one occurence of each
result=i;//longest prefix is the index
}
应该是这样的：
if(nX==nY)//same number of X and Y
result=i;//longest prefix is the index
}
没有检查nX!=0.因此，如果X没有出现在数组中和/或Y没有出现在数组中，则代码会不必要地返回 −1。
此外，这些需求似乎并不能保证X和Y是不同的;如果不是，那么你的代码返回 −1，但根据需求的字面解读，答案将是N−1。
在看到您的要求和答案后，您的代码@Joshua需要进行另一项更改。
@ruakh的答案也是正确的，但需要再做一次更改来处理其他测试用例。
对于 Y 的出现，您必须将"else if"条件替换为"if"条件，如下面的代码所示：
for(i=0;i<N;i++){
if(A[i]==X)
nX += 1;
if(A[i]==Y) //occurrence of Y
nY += 1;
因为，如果"X"和"Y"具有相同的值，并且只计算"nX"，则"nY"被忽略为"else if"条件。要解决这种情况，您必须将"else if"条件替换为"if"条件。
样本：X=42、Y=42、A=[42,63,42,6,2,13]
然后以我的条件，上面的样本得到了完美的处理。
我希望我的答案解决了或为您的答案增加了更多的准确性。
首先，在面试中从不做任何作业。面试不是考试。这是两个平等参与者的对话。忽略所有试图以这种方式操纵你和你的时间的公司。
二、这个函数声明
int solution(int X, int Y, int A[], int N);
是初学者的宣言。
首先不要使用大写字母来命名参数。
其次，数组的大小应具有函数的类型size_t和返回类型。
第三，数组应该是函数的第一个参数，并且应该具有限定符 const。
第四，在使用变量的最小范围内声明变量。
该函数可以按照演示程序中显示的方式进行声明。如果没有这样的前缀，该函数返回 0。如果没有前缀 ot 到 ( size_t ( -1，您可以根据需要将返回值更改为数组的大小。
#include <stdio.h>
size_t largest_balanced_seq( const int a[], size_t n, int x, int y )
{
size_t last_index = 0;
for ( size_t i = 0, x_count = 0, y_count = 0; i < n; i++ )
{
x_count += a[i] == x;
y_count += a[i] == y;
if ( x_count != 0 && x_count == y_count )
{
last_index = i;
}
}
return last_index;
}
int main(void)
{
int a[] = { 6, 42, 11, 7, 1, 42 };
printf( "%zun", largest_balanced_seq( a, sizeof( a ) / sizeof( *a ), 7, 42 ) );
int b[] = { 100, 63, 1, 6, 2, 13 };
printf( "%zun", largest_balanced_seq( b, sizeof( b ) / sizeof( *b ), 100, 63 ) );
return 0;
}
程序输出为
4
5
考虑到当函数返回子序列的长度时，即当它指定像[0, N)这样的范围时，它会好得多。例如，这种方法在整个C++中使用。所以谁给你这个任务不是一个很高的资格:)
int solution(int X, int Y, int A[], int N){
int result=-1;
int nX=0; //number of occurrences of X
int nY=0; //number of occurrences of Y
int i;
for(i=0;i<N;i++){//loop through the input array
if(A[i]==X)//occurrence of X
nX += 1;
/*
EDGE CASE BELOW: this should have been an if
statement, because X and Y could be the same
number. I know I missed this in the assessment,
but believe there is another issue, because I
failed almost all the test cases generated by the
assessment.
*/
else if(A[i]==Y)//occurrence of Y
nY += 1;
if((nX!=0)&& (nX==nY))//same number of X and Y
//and there is at least one occurence of each
result=i;//longest prefix is the index
if (X==Y)
result =i;
}---this two lines of code is needed for the code correction
return result;
}
def solution(X, Y, A):
N = len(A)
result = -1
nX = 0
nY = 0
for i in range(N):
if A[i] == X:
nX += 1
if A[i] == Y:
nY += 1
if nX == nY:
result = i
if (X == Y and nX != 0):
break
return result
print( solution(7, 42, [6, 42, 11, 7, 1, 42]) )
print( solution(6, 13, [13, 13, 1, 6]) )
print( solution(100, 63, [100, 63, 1, 6, 2, 13]) )
print( solution(1, 1, [1]) )
print( solution(1, 1, [1, 1, 1]) )
print( solution(1, 1, [1, 2, 1]) )
print( solution(1, 1, [2, 2, 1]) )
print( solution(1, 1, [2, 1, 2]) )
def solution(X, Y, A):
N = len(A)
result = -1
nX = 0
nY = 0
for i in range(N):
if X==Y:
if A[i]==X:
nX += 1
if nX%2==0:
result=i
else:
if A[i] == X:
nX += 1
elif A[i] == Y:
nY += 1
if nX == nY:
result = i
return result
print( solution(7, 42, [6, 42, 11, 7, 1, 42]))
print( solution(6, 13, [13, 13, 1, 6]) )
print( solution(100, 63, [100, 63, 1, 6, 2, 13]) )
print( solution(1, 1, [1]) )
print( solution(1, 1, [1, 1, 1]) )
目录：
4
-1
5
-1
1
int solution(int X, int Y, int[] A) {
int N = A.length;
int result = -1;
int nX = 0;
int nY = 0;
if (X != Y) {
for (int i = 0; i < N; i++) {
if (A[i] == X)
nX += 1;
else if (A[i] == Y)
nY += 1;
if (nX == nY)
result = i;
}
} else {
for (int i = 0; i < N; i++) {
if (A[i] == X){
nX += 1;
if(nX % 2 == 1 && nX > 1)
result = i - 1;
}
}
if (nX % 2 == 0)
result = N - 1;
}
return result;
}