2 回答

TA貢獻1862條經(jīng)驗 獲得超6個贊
該代碼給出了輸入的錯誤答案:
k = 2 array = [1, 2, 2, 1, 2, 2, 2, 2, 2]
更改應(yīng)該在第 18 行,即而不是
diff = max(d[j][0], r - d[j][-1]-1)
它應(yīng)該是
diff = max(d[j][0], n - d[j][-1]-1)
這是一個小錯誤,但導(dǎo)致很多測試用例失敗。

TA貢獻1874條經(jīng)驗 獲得超12個贊
考慮以下:
目標(biāo) = @,所有其他數(shù)字 = -。
A = { - - - @ - @ @ - - - - - - @ - @ - - - - - - - - - - - }
如果我們想找到不包含@的子數(shù)組,我們可以將整個數(shù)組視為被@包圍,這樣:
A` = { @ - - - @ - @ @ - - - - - - @ - @ - - - - - - - - - - - @ }
然后,這只是一個問題 - 跟蹤最后遇到的@的位置,以及連續(xù)兩次出現(xiàn)的@之間的最大差異。@ 可以是 1..k 之間的任何數(shù)字,因此可以通過大小為“k”的數(shù)組來跟蹤它。
C++ 代碼類似于(請測試 off-by-1 錯誤,因為我希望它在那里:
int subarr(int* A, size_t n, int k)
{
if (n < k)
{
return n;
}
size_t max = 0;
std::vector<size_t> lastPos(k);
for (size_t i = 0; i < lastPos.size(); i++)
{
lastPos[i] = -1;
}
// Find the longest subArray when excluding a single digit of the digits present.
for (size_t i = 0; i < n; i++)
{
if ((i - lastPos[A[i]]) > max)
{
max = i - lastPos[A[i]];
}
lastPos[A[i]] = i;
}
// Check for last
for (size_t i = 0; i < lastPos.size(); i++)
{
if ((i - lastPos[A[i]]) == -1)
{
return n;
}
}
return max - 1;
}
添加回答
舉報