algorithm - codility:峰值:在性能部件测试中实现go有什么问题？

Question

将数组划分为最大数目的相同大小的块，每个块应包含一个索引P，以使A [P-1] A [P + 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