递归:前缀总和

Question

我正在解决一个CodeWars的kata。

链接到卡塔

这是我的代码：

function partsSums(arr) {
let bigSum = [];
if (arr.length == 0) {
bigSum.push(0);
}
while (arr.length >= 1) {
let sum = arr.reduce((acc, ele) => acc + ele);
bigSum.push(sum);
partsSums(arr.shift());
}
return bigSum;
}

正确答案应该是：[20, 20, 19, 16, 10, 0]

我的函数返回：[ 20, 20, 19, 16, 10 ]

请指出我错在哪里或我的误解。谢谢！

Answer 1

您可以从右侧减少值，并将值添加到索引零处的值。

function partsSums(arr) {
return arr.reduceRight((r, value) => [r[0] + value, ...r], [0]);
}
console.log(partsSums([0, 1, 3, 6, 10]));

快速版本

function partsSums(ls) {
let l = ls.length,
result = [];
result[l] = 0;
while (l--) result[l] = result[l + 1] + ls[l];
return result;
}
console.log(partsSums([0, 1, 3, 6, 10]));

Answer 2

问题是，当你的数组在循环中达到长度 0 时，你实际上并没有将任何内容附加到bigSum。 您可以通过在循环后显式添加它来做到这一点。

function partsSums(arr) {
let bigSum = [];
while (arr.length >= 1) {
let sum = arr.reduce((acc, ele) => acc + ele);
bigSum.push(sum);
partsSums(arr.shift());
}

bigSum.push(0);
return bigSum;
}
console.log(partsSums([0, 1, 3, 6, 10]));

Answer 3

这是一个实际的递归，因为您已经用它标记了问题：

function f(A){
if (!A.length)
return [0];
const prev = f(A.slice(1));
return [A[0] + prev[0], ... prev];
}
console.log(f([0, 1, 3, 6, 10]));

Answer 4

for-loop遍历首尾相连。

function partsSums(arr) {
const res = [];
let sum = 0;
for (let i = arr.length; i > -1; i--) {
res[i] = sum += arr[i] || 0;
}
return res;
}
console.log(partsSums([0, 1, 3, 6, 10]));