c# - 数组的前向和后向搜索算法

Question

我正在研究一个简单的算法练习题，我试图弄清楚为什么在大约 20% 的测试用例中它失败了。因此，问题是，给定一个整数数组，找到数组中所有有效整数的平均值。

一个整数是有效的如果

1. 大于等于-273
2. 前两个或后两个整数中至少有一个与当前整数相差两个点

如果 int 无效，则不应将其包含在计算平均值中。另外，我不认为问题希望解决方案是循环的(不确定虽然只是在写这篇文章时考虑过它所以会尝试)即如果你在第一个 int array[0]，那么没有前两个 ints而不是最后两个是循环数组中的前两个。

我的策略总结在下面的代码中:

public double averageTemperature(int[] measuredValues)
{
    Queue<int> qLeft = new Queue<int>(2);
    Queue<int> qRight = new Queue<int>(2);

    double sum = 0d;
    int cnt = 0;

    for (int i = 0; i < measuredValues.Length; i++)
    {
        if (measuredValues[i] < -273)
            continue;
        if (qLeft.Count == 3)
            qLeft.Dequeue();
        for (int j = i + 1; j < measuredValues.Length; j++)
        {
            if (qRight.Count == 2)
            {
                break;
            }
            qRight.Enqueue(measuredValues[j]);
        }

        if (b(qLeft, qRight, measuredValues[i]) == true)
        {
            sum += measuredValues[i];
            cnt++;
            qLeft.Enqueue(measuredValues[i]);
        }


        qRight.Clear();
    }

    if (cnt > 0)
        return sum / cnt;
    return -300.0;
}
bool b(Queue<int> a, Queue<int> b, int c)
{
    foreach (int q in a)
    {
        if (Math.Abs(q - c) <= 2)
            return true;
    }
    foreach (int w in b)
    {
        if (Math.Abs(w - c) <= 2)
            return true;
    }
    return false;
}

但是，对于这个测试用例，我的策略失败了

{-13, 12, -14, 11, -15, 10, -16, 9, -17, 8, -18, 7, 6, -19, 5, -400, -400, 4, -390, -300, -270, 3, -12, 3, 2}

我不明白为什么。我错过了一些明显的东西吗？我知道它们可能是解决此问题的另一种更有效的方法，但在我知道为什么我的“天真”方法不起作用之前我不想尝试它们。

好吧，感谢你们，我终于明白了原因。这是我修改后的代码，供那些可能觉得有用的人使用:

public double averageTemperature(int[] measuredValues)
    {
        Queue<int> qLeft = new Queue<int>(2);
        Queue<int> qRight = new Queue<int>(2);

        double sum = 0d;
        int cnt = 0;


        for (int i = 0; i < measuredValues.Length; i++)
        {
            if (qLeft.Count == 3)
                qLeft.Dequeue();
            for (int j = i + 1; j < measuredValues.Length; j++)
              {
                if (qRight.Count == 2)
                {
                    break;
                }
                qRight.Enqueue(measuredValues[j]);
            }

            if (isValid(qLeft, qRight, measuredValues[i]) == true)
            {
                sum += measuredValues[i];
                cnt++;

            }
            qLeft.Enqueue(measuredValues[i]);
            qRight.Clear();
        }

        if (cnt > 0)
            return sum / cnt;
        return -300.0;
    }
    bool isValid(Queue<int> a, Queue<int> b, int c)
    {

        foreach (int q in a)
        {
            if (c >=-273 && Math.Abs(q - c) <= 2)
                return true;
        }
        foreach (int w in b)
        {
            if (c >=-273 && Math.Abs(w - c) <= 2)
                return true;
        }
        return false;
    }

Answer 1

尝试比较时从嵌套 for() 循环中的同一点开始。像这样:运行它会得到什么？

public double averageTemperature(int[] measuredValues)
{
Queue<int> qLeft = new Queue<int>(2);
Queue<int> qRight = new Queue<int>(2);

double sum = 0d;
int cnt = 0;

for (int i = 0; i < measuredValues.Length; i++)
{
    if (measuredValues[i] < -273)
        continue;
    if (qLeft.Count == 3)
        qLeft.Dequeue();
    for (int j = 0; j < measuredValues.Length; j++)
    {
        if (qRight.Count == 2)
        {
            break;
        }
        qRight.Enqueue(measuredValues[j]);
    }

    if (b(qLeft, qRight, measuredValues[i]) == true)
    {
        sum += measuredValues[i];
        cnt++;
        qLeft.Enqueue(measuredValues[i]);
    }


    qRight.Clear();
}

if (cnt > 0)
    return sum / cnt;
return -300.0;
}
bool b(Queue<int> a, Queue<int> b, int c)
{
foreach (int q in a)
{
    if (Math.Abs(q - c) <= 2)
        return true;
}
foreach (int w in b)
{
    if (Math.Abs(w - c) <= 2)
        return true;
}
return false;
}

是不是像以前一样每个方向都加一个，把你们两个分开？