javascript - Codility 中标志的 80% Javascript 解决方案

Question

Flags，Codility 中著名的代码挑战。

• Question Definition
• Official Answer
• My Test Report

我已经尝试了几次，我很确定错误是在函数“CheckFlags”内我也尝试过Codility提供的官方解决方案，最终得到了100%的解决方案。但是，我无法弄清楚为什么我的检查算法失败，并且只有三个失败的测试数据(检查测试报告)。

function solution(A) {

    let peakIndex = [];
    let peakCount = 0;

    for (let i = 1; i < A.length-1; i++) {
        if (A[i-1] < A[i] && A[i] > A[i+1]) {
            peakIndex[peakCount] = i;
            peakCount++;
        }
    }

    if (peakCount === 0 || peakCount === 1) 
        return peakCount;


    let left = 2;
    let right = peakCount;
    let result;

    while(right >= left) { // binary search

        let flags = Math.floor((left+right)/2)

        if (!CheckFlags(peakIndex, flags)) {
            right = flags - 1;    
        } else {
            result = flags;
            left = flags + 1;
        }
    }

    return result;
}

function CheckFlags (peakIndex, flags) {

    let flagCount = 1;
    let flagIndex = new Array(flags);
    flagIndex[0] = 0; // always include the first flag

    for (let peakIter = 1; peakIter < peakIndex.length && flagCount <= flags; peakIter++) {
        if (peakIndex[peakIter] - flagIndex[flagCount - 1] >= flags) {
            flagIndex[flagCount] = peakIndex[peakIter];
            flagCount++;

            if (flagCount === flags) 
                return true;
        }
    }

    return false;
}

Answer 1

问题出在行

flagIndex[0] = 0;

这行代码设置第一个标志索引的位置，但错误地分配了第一个位置而不是第一个峰值的位置。应该是这样的:

flagIndex[0] = peakIndex[0];