algorithm - 寻找严格递增的数字平方的边缘情况

Question

我正在尝试解决这个 codewars kata，Square into Squares。

我通过了大部分测试，但有两个输入我的算法超出了最大调用堆栈大小。

我觉得我正在处理所有边缘条件，但我不知道我遗漏了什么。

function sumSquares (n) {
  function decompose (num, whatsLeft, result) {
    if (whatsLeft === 0) return result
    else {
      if (whatsLeft < 0 || num === 0) return null
      else {
        return decompose(num-1, whatsLeft - num * num, [num].concat(result)) || decompose(num-1, whatsLeft, result)
      }
    }
  }
  return decompose(n-1, n*n, [])
}

const resA = sumSquares(50) //[1,3,5,8,49]
console.log(resA)
const resB = sumSquares(7) //[2,3,6]
console.log(resB)
const resC = sumSquares(11) //[ 1, 2, 4, 10 ]
console.log(resC)

const res1 = sumSquares(90273)
console.log(res1)
const res2 = sumSquares(123456)
console.log(res2)

Answer 1

看起来你的代码是正确的，但有两个问题:首先，你的调用堆栈最终会达到大小“num”(这可能导致你对大输入失败)，其次，它可能会多次重新计算相同的值次。

第一个问题很容易解决:您可以跳过 num 值，这会产生负的 whatsLeft 结果。像这样:

while(num * num > whatsLeft) num = num - 1;

您可以在第一个 if 语句之后插入它。这也使您能够删除对负 whatsLeft 的检查。作为一种风格，我在返回后删除了 if 语句的 else{} 案例——这减少了缩进，并且(我认为)使代码更易于阅读。但这只是个人品味问题。

function sumSquares (n) {
  function decompose (num, whatsLeft, result) {
    if (whatsLeft === 0) return result;
    while (num * num > whatsLeft) num -= 1;
    if (num === 0) return null;
    return decompose(num-1, whatsLeft - num * num, [num].concat(result)) || decompose(num-1, whatsLeft, result);
  }
  return decompose(n-1, n*n, []);
}

有了这些更改，您的测试用例会立即为我运行，因此没有必要解决第二个问题(可以通过内存解决)。我也尝试在 codewars 网站上提交它，并稍作调整(外部函数需要调用 decompose，因此外部和内部函数都需要重命名)，所有 113 个测试用例在 859ms 内通过.