动态编程:代码大战:两次线性:算法超时

Question

我正在与代码大战中的卡塔挣扎: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)