我正在尝试解决JavaScript中的hackerrank挑战,尽管对于大多数测试实例,我的解决方案表现良好,但我不断为其中一些超时(Hackerrank为JavaScript挑战设置了10秒)。该问题描述如下:
有N个孩子站成一排。最初,第 i 个孩子有一个[i] 糖果。有些孩子比其他孩子有更多的糖果。你有 以确保每个学生都有相同数量的糖果。合二为一 操作你可以告诉其中一个孩子给一个糖果 左邻,或右邻。您操作了多少次 需要确保每个学生都有相同数量的糖果吗?打印 尽可能少的操作数。输入是多行的 字符串,其中第一行包含单个整数 N,下一行包含单个整数 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 个测试用例(与之前由于超时而失败的测试用例相同)。这不是性能问题
问题是,你需要多少步才能为每个孩子计算平均数。
比如拿这行孩子来说,
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('5n1 4 2 7 1')); // 7
console.log(processData('5n7 4 2 1 1')); // 15
console.log(processData('3n1 2 3')); // 2