javascript - child 糖果 Hackerrank 挑战 : optimising the solution

Question

我正在尝试解决 hackerrank在 JavaScript 中挑战，虽然对于大多数测试实例，我的解决方案都执行得很好，但我不断地遇到其中一些的超时(Hackerrank 将其设置为 10 秒以用于 JavaScript 挑战)。问题描述如下:

There are N children standing in a line. Initially the i-th child has a[i] candies. Some of the children have more candies than others. You have to make sure that every student has the same number of candies. In one operation you can tell one of the children to give a single candy to the left neighbour, or to the right one. How many operations do you need to make sure every student has same number of candies? Print the minimal possible number of operations. The input is a multiline string, where the first line contains a single integer N, and the next line contains N space separated integers.

我通过计算应该给每个 child 多少糖果来解决这个问题，然后迭代包含糖果数量的数组，要么从最右边的位置抓取糖果(以防 child 吃不够), 或者将糖果传递到正确的位置(以防 child 吃的比需要的多)

这是我用于挑战的代码:

function processData(input) {
    let tmp = input.split(/\n| /),
        n = tmp[0]    

    tmp.shift()  // remove first element from tmp (the N variable)

    let s=0, a = tmp.map(function(ai) {novo=parseInt(ai, 10);s+=novo;return(novo)}),
        obj = s/n, ops = 0

    for(var i=0; i<n; i++) {

        if(a[i] > obj) {
            let moved = a[i]-obj
            a[i]-=moved
            a[i+1]+=moved
            ops+=moved
        }
        else {
            for(var j=i+1; a[i] != obj; j++) {


                if(a[j]===0) {
                    ops++
                }
                else {
                    let moved = Math.min(a[j], obj-a[i])
                    a[i]+=moved
                    a[j]-=moved
                    ops+=moved
                }
            }        
        }

        //console.log(a)
    }

    console.log(ops)
}

知道问题出在哪里吗？

你会如何优化我的代码？

挑战链接:https://www.hackerrank.com/contests/coc1/challenges/candies-1

编辑经过一些优化后，我的解决方案现在无法通过 3 个测试用例(与之前因超时而失败的测试用例相同)。这不是性能问题

Answer 1

问题是，您需要多少步才能使每个 child 的平均计数。

For example take this line of children,

1  4  2  7  1

where you start with the first children and look how much items it has and how many items it should have. Take the (absolute) difference for counting the moves and give the first child the average. The next children gets the delta of the first children. In this case after giving two items, it has then two items.

Then look at the next children in the line. Repeat the above and you get the count of moves for all children in a single loop.

   children     moves 
--------------- -----
 1  4  2  7  1     2
<3  2> 2  7  1     1
 3 <3  1> 7  1     2
 3  3 <3  5> 1     2
 3  3  3 <3  3>
--------------- -----
                   7

<x  y> denotes a group of changing values

Example 2

   children     moves 
--------------- -----
 7  4  2  1  1     4
<3  8> 2  1  1     5
 3 <3  7> 1  1     4
 3  3 <3  5> 1     2
 3  3  3 <3  3>
--------------- -----
                  15

function processData(input) {
    var [length, ...values] = input.split(/\\n|\s/),
        i,
        moves = 0,
        value = 0,
        sum = 0,
        avg;
        
    for (i = 0; i < +length; i++) sum += +values[i];
    avg = sum / length;

    for (i = 0; i < length - 1; i++) {
        value += +values[i];
        moves += Math.abs(value - avg);
        value -= avg;
    }
    
    return moves;
}

console.log(processData('5\n1 4 2 7 1')); //  7
console.log(processData('5\n7 4 2 1 1')); // 15
console.log(processData('3\n1 2 3'));     //  2