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

Question

我正在尝试解决这个 codewars 套路，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 的检查。作为一种风格，我在 return 之后删除了 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 个测试用例在 859 毫秒内通过。

Answer 2

@PaulHankin 的回答提供了很好的见解

让我们看看 sumSquares (n) 其中 n = 100000

decompose (1e5 - 1, 1e5 * 1e5, ...)

第一帧，

num = 99999
whatsLeft = 10000000000

哪个生成

decompose (99999 - 1, 1e10 - 99999 * 99999, ...)

第二帧在哪里

num = 99998
whatsLeft = 199999

这就是问题所在：上面的 num * num 显着大于 whatsLeft 并且每次我们重复尝试新的 num首先，我们每帧只减少 -1。不修复任何东西，下一个产生的进程将是

decompose (99998 - 1, 199999 - 99998 * 99998, ...)

第三帧在哪里

num = 99997
whatsLeft = -9999500005

看看 whatsLeft 是如何显着负面的？这意味着在下一个值不会导致 whatsLeft 低于零

之前，我们必须将 num 减少很多

// [frame #4]
num = 99996
whatsLeft = -9999000017

// [frame #5]
num = 99995   
whatsLeft = -9998800026

...

// [frame #99552]
num = 448
whatsLeft = -705

// [frame #99553]
num = 447
whatsLeft = 190

正如我们在上面看到的，仅仅猜测 sumSquares (100000) 的第二个数字就需要将近 100000 帧。这正是 Paul Hankin 描述的第一个问题。

如果我们只看 decompose 和 num，我们也可以更容易地想象它。下面，如果找不到解决方案，堆栈将增长到大小 num，因此不能用于计算 num 超过堆栈限制

的解决方案

// imagine num = 100000
function decompose (num, ...) {
  ...
  decompose (num - 1 ...) || decompose (num - 1, ...)
}

Paul 的解决方案使用 while 循环递减 num，直到 num 足够小。另一种解决方案是通过计算剩余 whatsLeft

的平方根来计算下一个 guess

const sq = num * num
const next = whatsLeft - sq
const guess = Math.floor (Math.sqrt (next))
return decompose (guess, next, ...) || decompose (num - 1, whatsLeft, ...)

现在它可用于计算 num 很大的值

console.log (sumSquares(123456))
// [ 1, 2, 7, 29, 496, 123455 ]

但请注意，某些输入存在错误。解决方案的平方总和仍然是正确的数量，但它允许重复一些数字

console.log (sumSquares(50))
// [ 1, 1, 4, 9, 49 ]

为了执行严格递增的要求，我们必须确保计算出的猜测仍然低于之前的猜测。我们可以使用 Math.min

<del>const guess = Math.floor (Math.sqrt (next))</del>
const guess = Math.min (num - 1, Math.floor (Math.sqrt (next)))

现在错误已修复

console.log (求和(50))
<del>// [1, 1, 4, 9, 49]</del>
// [ 1, 3, 5, 8, 49 ]

完整程序演示

function sumSquares (n) {
  function decompose (num, whatsLeft, result) {
    if (whatsLeft === 0)
      return result;
      
    if (whatsLeft < 0 || num === 0)
      return null;
    
    const sq = num * num
    const next = whatsLeft - sq
    const guess = Math.min (num - 1, Math.floor (Math.sqrt (next)))
    
    return decompose(guess, next, [num].concat(result)) || decompose(num-1, whatsLeft, result);
  }
  return decompose(n-1, n*n, []);
}

console.log (sumSquares(50))
// [ 1, 3, 5, 8, 49 ]

console.log (sumSquares(123456))
// [ 1, 2, 7, 29, 496, 123455 ]

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

Edge case for finding strictly increasing squares of a number

algorithm

recursion

callstack