Codility训练:用旋转时看起来相同的双手找出最大数量的时钟

Question

这是问题的链接:

https://codility.com/demo/take-sample-test/clocks

问题是我不能得到100分(只有42分).运行时间没问题,但是对于某些测试用例,代码给出了错误的答案,但我无法弄清楚问题是什么.有人可以帮帮我吗？

这是我的代码:

function rotate(arr) {
    var min = arr.reduce(function(a,b) { return a > b ? b : a });
    while (arr[0] != min) {
        var first = arr.shift();
        arr.push(first);
    }
}

function solution(A, P) {
    var positions = [];
    A.forEach(function(clock) {
        var position = [];
        clock.sort(function(a, b) { return a - b });
        clock.push(clock[0] + P);

        // calculating the distances between clock hands
        clock.forEach(function(hand, idx) {
            if (idx == 0) return;            
            position.push(clock[idx] - clock[idx - 1]);
        });

        // rotating the distances array to start with the minimum element
        rotate(position);
        positions.push(position);
    });

    //lexicographically sort positions array to similar types be consecutive
    positions.sort();

    var sum = 0;   
    // create a string to compare types with each other
    var type = positions[0].join(",");
    var n = 0;

    // counting consecutive positions with same type    
    positions.forEach(function(position, idx) {
        if (type == position.join(",")) {
            n++;
        } else {
            type = position.join(",");
            sum += (n * (n-1)) / 2;
            n = 1;
        }
    });
    sum += (n * (n-1)) / 2;

    return sum;
}

的jsfiddle

Answer 1

我认为这个问题的棘手之处在于“时钟”这个词，这让我在很长时间内只考虑两只手:)

“时钟”之间的相似性看起来可以通过“指针”分开的顺序来给出；在问题的示例中，差异为 1,2,1,1,2。然而，这个非常简单的案例很好地避免了主要问题区域......

换行：例如，在正常时间的时钟指针位于 4,6 和 11,1 处的距离均为 2；

多个指针：例如，具有 8 个点的 4 针时钟的指针可能位于 1、2、5、6 和 1、4、5、8，从而给出 1、3、1 或 3、1、3 的间隔，但这些指针在旋转上是相同的！

考虑具有大量指针的时钟，您可以想象指针之间的间隔序列不能简单地匹配或排序。

因此，我们测量双手之间的所有空间 - 上面的 4 手示例将是 1,3,1,3 和 3,1,3,1（为此，我只需将第一个元素添加到数组末尾）然后尝试将其与以前的模式进行匹配。我们只保留独特的模式以及每个模式的计数。

模式匹配尝试比较数组，然后将数组旋转一个元素并再次尝试（这会消耗大量时间！）

最后我们只是总结每个计数的组合。

当前代码的得分为 90，仅因超时而在几次测试中失败。我确信对 Javascript 有更好掌握的人可以将时间缩短几百毫秒。

这是输出：https://codility.com/demo/results/demo9GZ7VW-V63/

这是代码：

// compare 2 arrays - assumes they are the same length
function compareArrays( a1, a2 )
{
    for( var i=0; i<a1.length; i++)
        if( a1[i] != a2[i] ){
            return false;
        }
    return true;
}

// compare newpos[] with positions[][]
// - rotates newpos[] to attempt match 
// returns: index of match or -1 if no match
//
function comparePositions(positions,newpos)
{
    for(var ipos=0; ipos<positions.length; ipos++){
        for( i=0; i<newpos.length; i++){
            if( compareArrays(positions[ipos],newpos))
                return ipos;
            newpos.push(newpos.shift());    //rotate array
        }
    }
    return -1;
}

function solution(A, P) {
    var idx,diff,halfP=P/2;
    var highestCount=0;
    var highestIndex=0;
    var positions = [];
    var counts=[];
    A.forEach(function(clock) {
        var position = [];
        // sort 'hands' in ascending order
        clock.sort(function(a, b) { return a - b });
        // duplicate start point on end
        clock.push(clock[0]);

        // create array of distances between hands, wrapping around clock
        for(idx=1; idx<clock.length;idx++){
            diff= Math.abs(clock[idx] - clock[idx-1]);
            position.push((diff>halfP)?P-diff:diff);
        }

        idx= comparePositions(positions,position);
        if( idx < 0 ){
            positions.push(position);   // new pattern
            counts.push(1);
        }else{
            counts[idx]++;  // count old pattern
        }
    });

    // sum the combinations of counts for each position type
    var sum=0;
    for(idx=0; idx<counts.length; idx++){
        count=counts[idx];
        sum+= (count > 2) ? (count * (count-1))/2 : count-1;
    }

    return sum;
}