javascript - 动态规划 : Code Wars: twice linear: algorithm times out

Question

我在 Code Wars 中遇到了卡塔: https://www.codewars.com/kata/5672682212c8ecf83e000050/train/javascript
这个想法是创建一个数字序列，其中每个数字都是按照以下两个公式隐式创建的:

y=2x + 1  
z=3x + 1  

x 是序列中的当前数字。

从 1 开始，序列会像这样增长:

sequence = [1]  
x = 1  
y = 2*1 +1 = 3  
z = 3*1 + 1 = 4  
leading to sequence = [1, 3, 4]

将它应用到下一个数字会导致:

x = 3  
y = 2*3 + 1 = 7  
z = 3*3 + 1 = 10  
leading to sequence = [1, 3, 4, 7, 10]  

x = 4  
y = 2*4 + 1 = 9  
z = 3*4 + 1 = 13  
sequence [1, 3, 4, 7, 9, 10, 13]  

等等。请注意，我在最后一步对序列进行了排序，因为 x=4(9 和 13)的结果必须与 x=3(7 和 10)的结果混合以保持有序序列。

[1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]

我能够正确解决问题，但实现应该是高效的，但我超时了。我的代码:

function dblLinear(n) {
  cache = {};
  cache[0] = 1;
  res = [1];
  lengthCounter = 0
  if (n === 0) {
    return 1;
  }
  for (var i = 1; i < n + 10; i++) {
    //console.log("i ", i)
    if (cache[i] === undefined && res.includes(i)) {
      //console.log('i: ', i, ' el1: ', i * 2 + 1, ' el2: ', i * 3 + 1);
      cache[i] = [i * 2 + 1, i * 3 + 1]
      if (!res.includes(i * 2 + 1)) {
        res.push(i * 2 + 1);
      }
      if (!res.includes(i * 3 + 1)) {
        res.push(i * 3 + 1);
      }
      //console.log("res ", res)
    }
    if (res.length !== lengthCounter) {
      var arrStart = res.slice(0, Math.floor(res.length / 2));
      var arrEnd = res.slice(Math.floor(res.length / 2), res.length)
      arrEnd.sort(function(a, b) {
        return a - b;
      });
      res = arrStart.concat(arrEnd)
      lengthCounter = res.length
    }
  }
  //console.log('res ', res);
  return res[n];
}

正如您在我的代码中看到的那样，我尝试了一些简单的技巧来提高效率，但我猜我需要更多的速度增益。你认为问题是什么，我怎样才能提高效率？

任何帮助将不胜感激!

干杯

曼纽尔

Answer 1

这个问题可以在 O(n) 中解决。这个想法是跟踪最后生成的元素并添加两种可能性中较小的一种，因此元素按顺序添加。此代码轻松通过所有测试。

function dblLinear(n) {
    let u = [1], x = 0, y = 0
    for (let i = 0; i < n; i++) {
        let nextX = 2 * u[x] + 1, nextY = 3 * u[y] + 1
        if (nextX <= nextY) {
            u.push(nextX)
            x++
            if (nextX == nextY)
                y++
        } else {
            u.push(nextY)
            y++
        }
    }
    return u[n]
}

console.log(dblLinear(10) + " = " + 22)
console.log(dblLinear(20) + " = " + 57)
console.log(dblLinear(30) + " = " + 91)
console.log(dblLinear(50) + " = " + 175)
console.log(dblLinear(100) + " = " + 447)