codility:peaks:性能部件测试的go实现有什么问题？

Question

将一个数组分成最大数量的相同大小的块，每个块都应该包含一个索引P，使得AP - 1 < AP > AP +1。

我的解决方案：golang solution

然而，部分性能测试无缘无故地失败了，有人可以添加一些建议吗？

func Solution(A []int) int {
    peaks := make([]int, 0)
    for i := 1; i < len(A)-1; i++ {
        if A[i] > A[i-1] && A[i] > A[i+1] {
            peaks = append(peaks, i)
        }
    }

    if len(peaks) <= 0 {
        return 0
    }

    maxBlocks := 0

    // we only loop through the possible block sizes which are less than
    // the size of peaks, in other words, we have to ensure at least one
    // peak inside each block 
    for i := 1; i <= len(peaks); i++ {
        // if i is not the divisor of len(A), which means the A is not
        // able to be equally divided, we ignore them;
        if len(A)%i != 0 {
            continue
        }
        // we got the block size
        di := len(A) / i

        peakState := 0
        k := 0

        // this loop is for verifying whether each block has at least one
        // peak by checking the peak is inside A[k]~A[2k]-1
        // if current peak is not valid, we step down the next peak until
        // valid, then we move to the next block for finding valid peak;

        // once all the peaks are consumed, we can verify whether all the
        // blocks are valid with peak inside by checking the k value, 
        // if k reaches the 
        // final state, we can make sure that this solution is acceptable
        for {
            if peakState > len(peaks)-1 {
                break
            }
            if k >= i {
                break
            }
            if peaks[peakState] >= di*k && peaks[peakState] <= di*(k+1)-1 {
                peakState++
            } else {
                k++
            }
        }
        // if all peaks are checked truly inside the block, we can make
        // sure this divide solution is acceptable and record it in the
        // global max block size
        if k == i-1 && peakState == len(peaks) {
            maxBlocks = i
        }

    }
    return maxBlocks
}

Answer 1

感谢您在代码中添加更多注释。这个想法似乎是有道理的。如果法官报告了一个错误的答案，我会用随机数据、一些边缘案例和暴力控制来尝试，看看你是否能捕捉到一个合理大小的失败例子，并分析哪里出了问题。

到目前为止，我自己对一种可能的方法的想法是记录一个前缀数组，以便在O(1)中判断一个块是否有一个峰值。如果元素是峰值，则加1，否则加0。对于输入，

1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2

我们会有：

1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2
0  0  0  1  1  2  2  2  2  2  3  3

现在，当我们除法时，我们知道如果一个块包含一个峰值，如果它的相对和是正的：

  1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2
0|0  0  0  1| 1  2  2  2| 2  2  3  3
a          b           c           d

如果第一个块不包含峰值，我们会期望b - a等于0，但实际上我们得到了1，这意味着有一个峰值。这种方法将保证每个除数测试的O(num blocks)。

我要尝试的第二件事是从最小的除数(最大的块大小)迭代到最大的除数(最小的块大小)，但跳过可以被更小的除数除以失败的验证的除数。例如，如果2成功但3失败，那么6不可能成功，但4仍然可以。

1 2 3 4 5 6 7 8 9 10 11 12
2          |
3      |       |
6  |   |   |   |    |
4 x  |x    |    x|    x