时间戳

首页 > 解决方案 > 儿童糖果 Hackerrank 挑战：优化解决方案

javascript - 儿童糖果 Hackerrank 挑战：优化解决方案

问题描述

我正在尝试解决 JavaScript 中的hackerrank挑战，尽管对于大多数测试实例，我的解决方案都表现得相当好，但我一直在为其中一些实例设置超时（Hackerrank 将其设置为 10 秒用于 JavaScript 挑战）。问题描述如下：

有 N 个孩子排成一排。最初，第 i 个孩子有 a[i] 个糖果。有些孩子比其他孩子有更多的糖果。你必须确保每个学生都有相同数量的糖果。在一次操作中，您可以告诉其中一个孩子给左边的邻居或右边的一个糖果。您需要进行多少次操作才能确保每个学生拥有相同数量的糖果？打印尽可能少的操作数。输入是一个多行字符串，其中第一行包含一个整数 N，下一行包含 N 个空格分隔的整数。

我通过计算应该给每个孩子多少糖果来解决这个问题，然后迭代包含糖果数量的数组，或者从最右边的位置抓取糖果（以防孩子没有足够的糖果），或者将糖果传递到正确的位置（以防孩子超过需要）

这是我用于挑战的代码：

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 个测试用例（与之前由于超时而失败的相同）。这不是性能问题

标签： javascriptalgorithmoptimization

解决方案

问题是，您需要为每个孩子计算平均数。

比如拿这行孩子来说，

1  4  2  7  1

你从第一个孩子开始，看看它有多少项目，应该有多少项目。取（绝对）差来计算动作，给第一个孩子取平均值。下一个孩子获得第一个孩子的增量。在这种情况下，给出两个项目后，它就有两个项目。

然后看看排队的下一个孩子。重复上述操作，您将在一个循环中获得所有孩子的移动计数。

   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

示例 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

推荐阅读