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

问题描述

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

但是部分性能测试无缘无故失败，任何人都可以添加一些建议吗？

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
}

标签： algorithmgo

感谢您为您的代码添加更多注释。这个想法似乎有道理。如果法官报告了错误的答案，我会尝试使用随机数据和一些极端情况以及蛮力控制，看看你是否能抓住一个大小合理的失败示例，并分析哪里出了问题。

到目前为止，我自己对一种可能的方法的想法是记录一个前缀数组，以便判断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

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

问题描述

解决方案

推荐阅读