递归:前缀和

问题描述 投票:2回答:4

我正在解决CodeWars kata。

Link to the 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 ]

请指出我错了或我的误解。谢谢!

javascript arrays algorithm function recursion
4个回答
4
投票

您可以从右侧减少并在索引零处添加该值。

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]));

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]));

1
投票

这是实际的递归,因为您已经用这个标记了问题:

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]));

0
投票

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]));
© www.soinside.com 2019 - 2024. All rights reserved.